剑指Offer-调整数组顺序使奇数位于偶数前面

发表于 | 阅读次数 | 阅读数

调整数组顺序使奇数位于偶数前面

题目

输入一个整数数组，实现一个函数来调整该数组中数字的顺序，
使得所有的奇数位于数组的前半部分，所有的偶数位于位于数组的后半部分，
并保证奇数和奇数，偶数和偶数之间的相对位置不变。

思路

1.开辟新数组，分别两次遍历将奇数和偶数分开放入
2.利用插入排序的思想，找到当前偶数后面的第一个奇数，然后交换

代码

//方法1
public void reOrderArray_i(int [] array) {
    int[] newarray = new int[array.length];
    int m=0;
    for(int i=0;i<array.length;i++){
        if(array[i]%2!=0){
            newarray[m++]=array[i];
        }
    }

    for(int i=0;i<array.length;i++){
        if(array[i]%2==0){
            newarray[m++]=array[i];
        }
    }
    for(int i=0;i<newarray.length;i++){
        array[i]=newarray[i];
    }

}

//方法2
  public void reOrderArray(int[] nums){
    //找到左边的第一个偶数，然后偶数后面的找到第一个奇数
    for(int i=0;i<nums.length;i++){
        int target;
        if (nums[i]%2==0){
            for (int j=i;j<nums.length;j++){
                if (nums[j]%2==1){
                    target = nums[j];
                    while (j>i){
                        nums[j] = nums[j-1];
                        j--;
                    }
                    nums[j] = target;//此时j==i i也对
                    i++;
                }
            }
            break;
        }
    }
}
0%