力扣922题解法深度解析：双指针优化奇偶排序（含代码实现）

一、题目解读

力扣922题要求将给定数组按奇偶性重新排列，使得所有偶数位于奇数之前，同时保持原有相对顺序不变。例如，输入[4,5,2,7]应输出[4,2,5,7]。题目强调“原地”操作，即不得使用额外数组空间，需通过交换元素实现。

二、解题思路：双指针优化策略

核心思想是利用双指针分别遍历偶数位置和奇数位置，通过交换“错位”元素（即偶数位上的奇数或奇数位上的偶数），在保证相对顺序的前提下完成排序。此解法避免了频繁遍历和判断，时间复杂度降至O(n)。

三、解题步骤详解

1. 初始化指针：even=0（偶数位指针）、odd=1（奇数位指针）。

2. 外层循环：当两指针均未越界时，执行以下操作：

○ 偶数位优化：若当前even位置元素为偶数，直接跳过2个位置（因偶数位后续必为奇数位）。

○ 奇数位优化：若当前odd位置元素为奇数，同样跳过2个位置。

○ 交换条件：当两指针均有效且对应元素“错位”（如偶数位为奇数、奇数位为偶数）时，交换二者。

3. 循环终止：最终返回排序后的原数组。

四、代码实现与注释

class Solution {
public:
    vector<int> sortArrayByParityII(vector<int>& nums) {
        int n = nums.size();
        int even = 0; // 偶数指针，初始指向第一个偶数位置(索引0)
        int odd = 1;  // 奇数指针，初始指向第一个奇数位置(索引1)
        
        while (even < n && odd < n) {
            // 找到偶数位置上不是偶数的元素
            while (even < n && nums[even] % 2 == 0) {
                even += 2; // 跳过正确位置的偶数
            }
            // 找到奇数位置上不是奇数的元素
            while (odd < n && nums[odd] % 2 == 1) {
                odd += 2; // 跳过正确位置的奇数
            }
            // 交换这两个位置上的元素
            if (even < n && odd < n) {
                swap(nums[even], nums[odd]);
            }
        }
        return nums;
    }
};

代码关键点：

● 通过even += 2和odd += 2跳过已符合奇偶性的元素，避免重复判断；

● 交换条件仅当两指针均有效时触发，确保边界安全。

五、总结

本解法通过双指针机制实现“原地”奇偶排序，兼具高效性（O(n)时间复杂度）与简洁性。其核心在于利用位置索引的奇偶性作为判断依据，避免了额外的标记或遍历操作。在实际应用中，此类双指针优化策略可扩展至其他需要保持相对顺序的排序场景。