# 75 - Sort Colors

解法一 - Two Pointer

這題也算是 Two Pointer 的經典題了,如果用 in-place 的 sort 方法(例如 heap sort),就得花 O(NlogN) 的時間,但如果用 Two Pointer,可以將時間複雜度降到 O(N)。

以下分別用 for 跟 while 兩種不同的實作方法,確保自己通達整個過程:

class Solution {
public:
    void sortColors(vector<int>& nums) {
        int n=nums.size(), l=0, r=n-1;

        for(int i=0; i<=r; ) {
            if(nums[i] == 0) {
                swap(nums[l], nums[i]);
                l++;

                // because we scan from left to right
                // after swap, nums[i] can only be 0 or 1
                // so we can increment i by 1 without worrying nums[i[ being 2
                i++; 
            }
            else if(nums[i] == 2) {
                swap(nums[r], nums[i]);
                r--;
            }
            else {
                i++;
            }
        }
    }
};
class Solution {
public:
    void sortColors(vector<int>& nums) {
        int p0 = 0, cur = 0;
        int p2 = nums.size()-1;

        while(cur <= p2) {
            if(nums[cur] == 0) swap(nums[p0++], nums[cur++]);
            else if(nums[cur] == 2) swap(nums[p2--], nums[cur]);
            else cur++;
        }
    }
};

Last updated