LeetCode 75. Sort Colors [Medium] [C++] 解題筆記

這題給定一個與有 0, 1, 2 三種元素的 array nums，要求我們在 O(1) space 的限制下將其排序。

EX:

        Input: [2,0,2,1,1,0]

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

想法:

        最簡單的當然就是用STL sort() 拉哈哈哈。 題目下方有給提示說可以用 counting sort，

這也是相對比較直覺的作法，宣告一個 vector，然後紀錄每個數字的出現次數，再從頭

重新擺放這些元素就行了。

另一種不需要額外空間的作法是使用 Two pointers，分別宣告一個 zero 變數表示 0 的最後一個位置

(所有在 nums[zero] 前的元素都是0，不包含 nums[zero])與一個 second 變數表示 2 的第一個位置

(所有在 nums[second] 後的元素都是2，不包含 nums[second])，然後從頭開始遍歷，

遇到 2 就跟 second 指向的元素交換，遇到 0 就跟 zero 指向的元素交換。

特別注意解法二中的while loop 順序是不能變動的，因為 2 的交換有可能會把後面的0換到

中間，然後 i++ 之後遍歷結束就漏掉了，而 0的交換不會有這個問題，

因為 0 是排在前面的所以0要交換的對像如果本來是2則早在交換前它就換先被換到後面去了。

(ex: [1, 2, 0] -> [1, 0, 2] 先換0的話)

Time Complexity: O(n)

完整程式碼:

解法一 (counting sort):

class Solution {
public:
    void sortColors(vector<int>& nums) {
        vector<int> cnt(3, 0);
        for (int i = 0; i < nums.size(); i++) {
            cnt[nums[i]]++;
        }
        int j = 0;
        for (int i = 0; i < cnt.size(); i++) {
            int cur = j;
            for (; j < cnt[i] + cur; j++) {
                nums[j] = i;
            }
        }
    }
};

解法二 (two pointers):

class Solution {

public:    

    void sortColors(vector<int>& nums) {

        // the start position of 2, all element after second are 2 (exclude second)

        int second = nums.size()-1;

        // the end position of 0, all elements before zero are 0 (exclude zero)

        int zero = 0;

        for (int i = 0; i < nums.size(); i++) {

            while (nums[i] == 2 && i < second) {

                swap(nums[i], nums[second--]);

            }

            while (nums[i] == 0 && i > zero) {

                swap(nums[i], nums[zero++]);

            }

        }

    }

};