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

题目描述

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

空间换时间,时间复杂度O(n),空间复杂度O(n)

public void reOrderArray(int [] array) {
    int[] ans = new int[array.length];
    int[] oddList = new int[array.length];
    int[] evenList = new int[array.length];
    int oddNum = 0, evenNum = 0;
    for (int i = 0; i < array.length; i++) {
        if (array[i] % 2 == 1) {
            oddList[oddNum++] = array[i];
        } else {
            evenList[evenNum++] = array[i];
        }
    }
    for (int k = 0; k < oddNum; k++) {
        ans[k] = oddList[k];
    }
    for (int k = 0; k < evenNum; k++) {
        ans[k + oddNum] = evenList[k];
    }

    for (int i = 0; i < ans.length; i++) {
        array[i] = ans[i];
    }
}

网上题解

链接：https://www.nowcoder.com/questionTerminal/beb5aa231adc45b2a5dcc5b62c93f593?answerType=1&f=discussion
来源：牛客网

思路：参考快速排序

• i++往前走碰到偶数停下来，j = i+1
• 若a[j]为偶数，j++前进，直到碰到奇数
• a[j]对应的奇数插到a[i]位置，j经过的j-i个偶数依次后移
• 如果j==len-1时还没碰到奇数，证明i和j之间都为偶数了，完成整个移动

class Solution {
public:
    void reOrderArray(vector<int> &array) {
        int len = array.size();
        if(len <= 1){ // 数组空或长度为1
            return;
        }

        int i = 0;
        while(i < len){
            int j = i + 1;
            if(array[i]%2 == 0){ // a[i]为偶数，j前进，直到替换
                while(array[j]%2 == 0){ // j为偶数，前进
                    if(j==len-1)// i为偶数，j也为偶数，一直后移到了末尾，证明后面都是偶数
                         return;
                    j++;
                }
                // 此时j为奇数
                int count = j-i;
                int temp = array[i];
                array[i] = array[j];
                while(count>1){
                    array[i+count] = array[i+count-1];//数组后移
                    count--;
                }
                array[i+1] = temp;
            }
            i++;
        }
    }
};