leetcode：922. 按奇偶排序数组 II

题目

给定一个非负整数数组 nums， nums 中一半整数是 奇数 ，一半整数是 偶数 。
对数组进行排序，以便当 nums[i] 为奇数时，i 也是 奇数 ；当 nums[i] 为偶数时， i 也是 偶数 。
你可以返回 任何满足上述条件的数组作为答案 。

进阶：可以不使用额外空间解决问题吗？

示例：

输入：nums = [4,2,5,7]
输出：[4,5,2,7]
解释：[4,7,2,5]，[2,5,4,7]，[2,7,4,5] 也会被接受。

输入：nums = [2,3]
输出：[2,3]

解答 & 代码

解法一：两次遍历

1. 双指针，类似快排分割函数，将奇数全部位于数组左边，偶数全部位于数组右边
2. 双指针，当 left 为偶数时，交换 nums[left]、nums[right]。 就得到满足题意的数组：奇数位上是奇数，偶数位上是偶数

class Solution {
public:
    vector<int> sortArrayByParityII(vector<int>& nums) {
        // 1. 双指针，类似快排分割函数，将奇数全部位于数组左边，偶数全部位于数组右边
        int temp = nums[0];
        int left = 0;
        int right = nums.size() - 1;
        while(left < right)
        {
            while(left < right && nums[right] % 2 == 0)
                --right;
            nums[left] = nums[right];

            while(left < right && nums[left] % 2 == 1)
                ++left;
            nums[right] = nums[left];
        }
        nums[left] = temp;

        // 2. 双指针，当 left 为偶数时，交换 nums[left]、nums[right]
        // 就得到满足题意的数组：奇数位上是奇数，偶数位上是偶数
        left = 0;
        right = nums.size() - 1;
        while(left < right)
        {
            swap(nums[left], nums[right]);
            left += 2;
            right -=2 ;
        }

        return nums;
    }
};

复杂度分析：设数组长为 N

• 时间复杂度 O(N)：两次遍历
• 空间复杂度 O(1)：

执行结果：

执行结果：通过

执行用时：12 ms, 在所有 C++ 提交中击败了 95.51% 的用户
内存消耗：20.9 MB, 在所有 C++ 提交中击败了 65.42% 的用户

解法二：一次遍历

class Solution {
public:
    vector<int> sortArrayByParityII(vector<int>& nums) {
        int evenIdx = 0;    // 偶数下标
        int oddIdx = 1;        // 奇数下标
        while(evenIdx < nums.size())
        {
            // 如果当前偶数下标指向的是奇数
            if(nums[evenIdx] % 2 == 1)
            {
                // 则移动奇数下标（每次移动两格），直到奇数下标指向偶数
                while(nums[oddIdx] % 2 == 1)
                    oddIdx += 2;
                // 交换偶数下标和奇数下标指向的两个数
                swap(nums[evenIdx], nums[oddIdx]);
            }
            //偶数下标走两步
            evenIdx += 2;
        }
        return nums;
    }
};

复杂度分析：设数组长为 N

• 时间复杂度 O(N)：一次遍历
• 空间复杂度 O(1)：

执行结果：

执行结果：通过

执行用时：16 ms, 在所有 C++ 提交中击败了 81.52% 的用户
内存消耗：20.9 MB, 在所有 C++ 提交中击败了 46.94% 的用户