在一个数组中的元素大多奇数和偶数是混在一起的，而将数组中元素奇数和偶数分开存放则是我们要解决的问题。
 
       将奇数和偶数分开存放然后打印出来的思路是先创建两个空间，将奇数和偶数分别存放起来，然后再将他们又存进原数组，最后将数组元素循环打印就完成了奇数和偶数的分别存放。
 
#include<stdio.h>
int main()
{
	int arr[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9 };
	int i = 0;
	int j = 0;
	int k = 0;
	int sz = sizeof(arr) / sizeof(arr[0]);
	int arr2[10] = { 0 };
	int arr3[10] = { 0 };
	while (i < sz)
	{
		if (arr[i] % 2 == 1)
		{
			arr2[j] = arr[i];
			j++;
			i++;
		}
    	else
		{
			arr3[k] = arr[i];
			k++;
			i++;
		}
	}
	i = 0;
	j --;
	k --;
	while (j != -1)
	{
		arr[i] = arr2[j];
		j--;
		i++;
	}
	while (k != -1)
	{
		arr[i] = arr3[k];
		i++;
		k--;
	}
	for (i = 0; i < sz; i++)
	{
		printf("%d ", arr[i]);
	}
	system("pause");
	return 0;
}
 

       输入一个整数数组，实现一个函数，来调整该数组中数字的顺序使得数组中所有的奇数位于数组的前半部分，所有偶数位于数组的后半部分。
 
       数组奇数位于前半部分，偶数位于后半部分，实现这个需要用到循环，在写函数时，要知道奇数和偶数满足的条件是什么，循环开始当满足前半部分下标小于后半部分下标（first<end）时，如果前面的数是奇数则下标往前再走一个，重复执行，直到遇到偶数，下标不动，后半部分下标开始，如果是偶数，则下标往前走，直到遇到一个奇数，下标满足交换条件，则把这两个数交换，使奇数位于前面，偶数换到后面。
 
程序如下：
 
#include <stdio.h>
#include <string.h>
#include <assert.h> 
int swap(int *x, int *y)   //交换两个变量的内容
{
	int tmp;       
	tmp = *x;
	*x = *y;
	*y = tmp;
}
void show(int arr[], int length)   //打印arr的内容
{
	assert(arr);    
	int i = 0;
	for (i = 0; i < length ; i++)
	{
		printf("%d ", arr[i]);
	}
	printf("\n");

}
int *newline(int *arrold,int len )
{
	assert(arrold);
	int first = 0;
	int end = len - 1;
	int i = 0;
	while (first < end)
	{
		while ((first < len) && (first<end) && (arrold[first] & 1))
		{
			first++;   //如果是奇数，则执行循环体内容
		}
		while ((end>first) && (end>0) && !(arrold[end] & 1))
		{
			end--;   //如果是偶数执行循环体内容
		}
		if (first < end)
		{
			swap(&arrold[first], &arrold[end]);   //前一个数是偶数，后一个数是奇数，交换两数
			first++;    //前面下标往后移，后面前移
			end--;
		}
	}
}
int main()
{
	int array[] = { 0, 1, 2, 3, 4, 5, 6, 7, 8, 945,66,76,33 };
	int len = sizeof(array) / sizeof(array[0]);
	show(array, len);     //奇偶交换前打印一下
	newline(array,len);   
	show(array, len);
	system("pause");
	return 0;
}
 

 
 
 

 运行结果如下图：
 

 
 

 
 

 

学而不思则罔，思而不学则殆
 


 
【算法】【数组】删除数组中偶数下标的元素，返回奇数下标的元素
 
题目
解法一
解法二
解法三 - 双指针法
三种算法效率比较

 
 
题目
 
 
 
删除ArratList中索引为偶数的节点
 输入：
 [1,2,3]
 输出：
 [2]
 
 
void removeItemsWithEvenIndex(ArrayList<Integer> list) {
}
 
注意：list既是输入，也是输出
 
解法一
 
思路：通过iterator迭代删除
 时间复杂度:$$O(n^2)$$
 空间复杂度:$$O(1)$$
 
    static void removeItemsWithEvenIndex1(ArrayList<Integer> list) {
        Iterator<Integer> iterator = list.iterator();
        int index = 0;
        while (iterator.hasNext()) {
            iterator.next();
            if (index % 2 == 0) {
                iterator.remove();
            }
            index++;
        }
    }
 
解法二
 
思路：复制一份数据tmpList,把原有list列表清空，再把tmpList中奇数索引的元素加入到list中
 时间复杂度：$$O(n)$$
 空间复杂度：$$O(n)$$
 
    static void removeItemsWithEvenIndex2(ArrayList<Integer> list) {
        //copy一份
        ArrayList<Integer> tmpList = new ArrayList<Integer>(list);
        list.clear();
        //获取偶数节点
        for (int index = 0; index < tmpList.size(); index++) {
            if (index % 2 != 0) {
                list.add(tmpList.get(index));
            }
        }
    }
 
解法三 - 双指针法
 
思路：双指针法标记，把奇数索引位置的元素前移。慢指针指向需要填充的位置，快指针遇到偶数索引跳过，奇数索引就把位置的元素复制到慢指针位置。
 时间复杂度：$$O(n)$$
 空间复杂度：$$O(1)$$
 
    static void removeItemsWithEvenIndex3(ArrayList<Integer> list) {
        //
        int index = 0;
        for (int i = 0; i < list.size(); i++) {
            if (i % 2 != 0) {
                //奇数下标数据前移
                list.set(index++, list.get(i));
            }
        }
        //移除[index , list.size())的数据
        if (list.size() > index) {
            list.subList(index, list.size()).clear();
        }
    }
 
三种算法效率比较
 
算法\数量
100
1000
1w
10w
20w
30w
40w
50w
60w
70w
80w
90w
100w
200w
500w
1000w
2000w
5000w
算法一
0
0
5
535
2220
4882
8842
13648
19537
26423
33950
44380
54999
-
-
-
-
-
算法二
0
0
1
5
5
6
8
8
9
10
10
10
13
16
140
38
72
224
算法三
0
0
1
5
5
5
5
6
7
7
7
8
8
10
18
24
39
87
随着数量的增加，第一种算法已经不能看了，直接砍掉。二三种时间差距不大，主要是空间消耗。
 测试代码：
 
    public static void main(String[] args) {
        ArrayList<Integer> list = new ArrayList<Integer>();
        for (int i = 0; i < 50000000; i++) {
            list.add(i);
        }
        System.out.println(list.size());

        ArrayList<Integer> list1 = new ArrayList<>(list);
        ArrayList<Integer> list2 = new ArrayList<>(list);
        ArrayList<Integer> list3 = new ArrayList<>(list);

        long start = System.currentTimeMillis();
        removeItemsWithEvenIndex3(list1);
        long end = System.currentTimeMillis();
        System.out.println(list1.size() + " " + (end - start));


        start = System.currentTimeMillis();
        removeItemsWithEvenIndex2(list2);
        end = System.currentTimeMillis();
        System.out.println(list2.size() + " " + (end - start));


        start = System.currentTimeMillis();
        removeItemsWithEvenIndex1(list3);
        end = System.currentTimeMillis();
        System.out.println(list3.size() + " " + (end - start));

        System.out.println(list1.equals(list2));
        System.out.println(list1.equals(list3));
    }

//删除数组中的奇数 method 1
function deleteOdd(arr){
    var newArray = [];
    for(var i=0;i<arr.length;i++){
        if(arr[i]%2==0){
            newArray.push(arr[i]);
        }
    }
    return newArray;
}
var numbers = [11,22,33,44,55,66];
console.log(deleteOdd(numbers));// [22, 44, 66]


//删除数组中的奇数 method 2
function deleteOdd(arr){
    for(var i = 0;i<arr.lenght;i++){
        if(arr[i]%2==1){
            arr.splice(i,1);
            i--;
        }
    }
    return arr;
}
var numbers=[1,2,3,4,5,6];
console.log(deleteOdd(numbers));//问题待解决