922. 按奇偶排序數組 II

思路

題目要把數字放到正確的位置上，奇數放到奇數下標，偶數放到偶數下標。
因此創建兩個指針，各自指向奇數與偶數的位置，並檢查當前放置的數字是否正確。
由於題目確保每個數字都有對應的位置，所以放置錯誤的數字一定是成對的。

除此之外，也能「盯著最後一個位置看」，將它視作分發的節點，把數字分發到對應的位置上。

程式碼

1. 雙指針

class Solution {
public:
    vector<int> sortArrayByParityII(vector<int>& nums) {
        int n = nums.size();
        int i = 0, j = 1;
        while(i < n) {
            while(i < n && nums[i] % 2 == 0) { // 找放到偶數位置的奇數
                i += 2;
            }
            while(j < n && nums[j] % 2 == 1) { // 找放到奇數位置的偶數
                j += 2;
            }
            if(i < n && j < n) { // 由於錯誤數字必定成對，這裡可以只判斷 i 或只判斷 j 
                swap(nums[i], nums[j]);
                i += 2;
                j += 2;
            }
        }
        return nums;
    }
};

2. 雙指針 分發

class Solution {
public:
    vector<int> sortArrayByParityII(vector<int>& nums) {
        int n = nums.size();
        for(int even = 0, odd = 1; odd < n && even < n;) {
            if(nums.back() & 1) {
                swap(nums[odd], nums.back());
                odd += 2;
            }
            else {
                swap(nums[even], nums.back());
                even += 2;
            }
        }
        return nums;
    }
};

複雜度分析

• 時間複雜度：$O(n)$
• 空間複雜度：$O(1)$