21.调整数组顺序使奇数位于偶数前面(一).md

21.调整数组顺序使奇数位于偶数前面(一)

题目描述

输入一个长度为 n 整数数组，数组里面不含有相同的元素，实现一个函数来调整该数组中数字的顺序，使得所有的奇数位于数组的前面部分，所有的偶数位于数组的后面部分，并保证奇数和奇数，偶数和偶数之间的相对位置不变。

示例1

输入：[1,2,3,4]
返回值：[1,3,2,4]

示例2

输入：[2,4,6,5,7]
返回值：[5,7,2,4,6]

示例3

输入：[1,3,5,6,7]
返回值：[1,3,5,7,6]

思路 & 解答

空间换时间

用空间换时间做法，就是新建一个数组，copy一份，先计算出奇数的个数，也就是能够知道第一个偶数应该放在数组的哪一个位置，然后再遍历一次，依次放到对应的位置即可。

Java 代码如下：

public class Solution {
    public int[] reOrderArray(int[] nums) {
        // 奇数个数
        int oddCnt = 0;
        for (int x : nums)
            if (x % 2 == 1)
                oddCnt++;
        int[] copy = nums.clone();
        int i = 0, j = oddCnt;
        for (int num : copy) {
            if (num % 2 == 1)
                nums[i++] = num;
            else
                nums[j++] = num;
        }
        return nums;
    }
}

C++ 代码如下：

class Solution {
public:
    vector<int> reOrderArray(vector<int>& array) {
        // 奇数个数
        int oddCnt = 0;
        for (int x : array)
            if (x % 2 == 1)
                oddCnt++;
        vector<int> copy = array;
        int i = 0, j = oddCnt;
        for (int num : copy) {
            if (num % 2 == 1)
                array[i++] = num;
            else
                array[j++] = num;
        }
        return array;
    }
};

冒泡

第二种做法，时间复杂度为O(n²),类似冒泡，将找到的奇数不断往前面冒泡，直到前面排好奇数的位置，空间复杂度为 O(1)，没有使用额外的空间。

Java代码如下：

public class Solution {
    public void reOrderArray(int [] array) {
        // 已经摆好的奇数个数
        int numOfOdd = 0;
        for (int i = 0; i < array.length; i++) {
            if (array[i] % 2 == 1) {
                int j = i;
                // 往前面冒泡
                while (j > numOfOdd) {
                    int tmp = array[j];
                    array[j] = array[j-1];
                    array[j-1] = tmp;
                    j--;
                }
                numOfOdd++;
            }
        }
        return array;
    }
}

C++ 代码如下：

class Solution {
public:
    vector<int> reOrderArray(vector<int> &array) {
        // 已经摆好的奇数个数
        int numOfOdd = 0;
        for (int i = 0; i < array.size(); i++) {
            if (array[i] % 2 == 1) {
                int j = i;
                // 往前面冒泡
                while (j > numOfOdd) {
                    int tmp = array[j];
                    array[j] = array[j - 1];
                    array[j - 1] = tmp;
                    j--;
                }
                numOfOdd++;
            }
        }
        return array;
    }
};