runtime 0 ms, beats 100% of cpp submissions
O(n) solution with explanation

tags: two pointer

Sort Colors

📖 description

給定一個只包含 0、1、2 的陣列，要求 sort 該陣列，並且只能遍歷一次陣列且不使用額外空間。

ex.
    Input: 
        nums = [2,0,2,1,1,0]

    Output: [0,0,1,1,2,2]

🧠 solution

使用雙指標， zeros 負責記錄 0 的尾巴， twos 負責記錄 2 的開頭

  • 當前元素為 0 ，與 zeros 交換
  • 當前元素為 1 ，不操作
  • 當前元素為 2 ，與 twos 交換，並不移動 (因為交換過來的元素會有其他可能)

且我們其實不用遍歷整個陣列，因為只要碰到 twos 就代表後方一定是一串 2 了

這樣交換完後左方一定是一串 0 ，右方一定是一串 2 ，而 1 因為不移動，所以會在中間

⏳ time complexity

遍歷一次陣列，時間複雜度 O(n)
總時間複雜度 O(n)

📝 code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
    void sortColors(vector<int>& nums) {
        int zeros = 0,twos = nums.size()-1;
        for(int i=0;i<=twos;++i){   // 只需要做到 2 的開頭即可
            if(nums[i] == 0){
                swap(nums[i],nums[zeros]);
                ++zeros;
            }
            else if(nums[i] == 2){
                swap(nums[i],nums[twos]);
                --twos;
                --i;    // 不移動
            }
        }
    }
};