剑指21：调整数组顺序奇数位于偶数前面

传送门

nowcoder
leetcode

题目描述

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

C++ 代码 - nowcoder

/*
    新开辟一个临时数组保存数据

    时间复杂度：O(n)
    空间复杂度：O(n)
*/
class Solution {
public:
    void reOrderArray(vector<int>& array) {
        int n = array.size();
        vector<int> temp(n, 0);
        int index = 0;
        for (int i = 0; i < n; i ++) {
            if ((array[i] & 1) == 1) {
                temp[index ++] = array[i];
            }
        }
        for (int i = 0; i < n; i ++) {
            if ((array[i] & 1) == 0) {
                temp[index ++] = array[i];
            }
        }

        array.assign(temp.begin(), temp.end());
    }
};

/*
    原地解法：
        类似于冒泡排序。
        前偶后奇就进行交换，这样一次可以将第一个奇数放在首位，同时最后一个偶数放在末尾。
    
    时间复杂度：O(n^2)
    空间复杂度：O(1)
*/
class Solution {
public:
    void reOrderArray(vector<int> &array) {
        int n = array.size();
        for (int i = 0; i < n; i ++) {
            for (int j = n - 1; j > i; j --) {
                if (array[j] % 2 == 1 && array[j - 1] % 2 == 0) {
                    swap(array[j], array[j - 1]);
                }
            }
        }
    }
};

C++ 代码 - leetcode

/*
    双指针（改变了奇数和奇数，偶数和偶数之间的相对位置）

    时间复杂度：O(n)
    空间复杂度：O(1)
*/
class Solution {
public:
    vector<int> exchange(vector<int>& nums) {
        if (nums.size() == 0) return vector<int>();

        int left = 0, right = nums.size() - 1;
        while (left < right) {
            while (left < right && !isEven(nums[left])) left ++;
            while (left < right && isEven(nums[right])) right --;
            if (left < right) swap(nums[left ++], nums[right --]);
        }
        return nums;
    }

    bool isEven(int n) {
        return (n & 1) == 0;
    }
};

/*
	思路同上
*/
class Solution {
public:
    vector<int> trainingPlan(vector<int>& nums) {
        // 维护 nums[0, slow) 都是奇数
        int fast = 0, slow = 0;
        while (fast < nums.size()) {
            // fast 遇到奇数，交换 nums[fast] 与 nums[slow]
            if (nums[fast] % 2 == 1) {
                int temp = nums[slow];
                nums[slow] = nums[fast];
                nums[fast] = temp;
                slow ++;
            }
            fast ++;
        }
        return nums;
    }
};