75. Sort Colors - cocoder39/coco39_LC GitHub Wiki

75. Sort Colors

Notes 2020: Option 1: quick sort

class Solution:
    def sortColors(self, nums: List[int]) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        n = len(nums)
        i, p0, p2 = 0, 0, n-1
        while i <= p2:
            if nums[i] == 0:
                nums[i], nums[p0] = nums[p0], nums[i] 
                p0 += 1
                i += 1
            elif nums[i] == 2:
                nums[i], nums[p2] = nums[p2], nums[i] 
                p2 -= 1
            else:
                i += 1

Option 2: bucket sort

===============================================================

[lt, gt] are 1, left side are 0, right side are 2, the trick is when should we use i++. i records currently visited number, which should be faster than lt. i >= lt

  • nums[i++] < nums[lt++], here we have to use i++, because the new nums[i] (previous nums[lt]) should have been visited by i

O(n) time and O(1) space

void sortColors(vector<int>& nums) {
        int sz = nums.size();
        int i = 0, lt = 0, gt = sz - 1;
        while (i <= gt) {
            if (nums[i] == 0) {
                swap(nums[lt++], nums[i++]); //nums[lt] is guaranteed to be visited by i => i++
            } else if (nums[i] == 2) {
                swap(nums[gt--], nums[i]); //nums[gt] has not been visited by i => not i++
            } else {
                i++;
            }
        }
    }

bucket sort works as well

void sortColors(vector<int>& nums) {
        vector<int> counter(3);
        for (auto num : nums) {
            counter[num]++;
        }
        
        int idx = 0;
        for (int i = 0; i < 3; i++) {
            for (int j = 0; j < counter[i]; j++) {
                nums[idx++] = i;
            }
        }
    }

second round attention:

  • condition of while depends on initial value of r and b, wrong condition would result in dead loop

b = sz => black is [b, sz) => do need care case when w == b => while (w < b), while(w <= b) leads to dead loop

b = sz - 1 => black is (b, sz) => need care case when w == b => while (w <= b), while(w < b) ignores nums[b]

  • when to increase w

when nums[w] == 1, increase

when nums[w] == 0, increase after swapping, because the new element at index w is either 0 (no swapping) or 1 (a previously processed element)

when nums[w] == 2, do not increase after swapping, because the new element at index w has not been visited before

void sortColors(vector<int>& nums) {
        int sz = nums.size();
        int r = 0, w = 0, b = sz - 1;
        //[0, r) is red, [r, w) is white, (b, sz-1] is black  
        while (w <= b) {
            if (nums[w] == 0) {
                swap(nums[r++], nums[w++]);
            } else if (nums[w] == 2) {
                swap(nums[b--], nums[w]);
            } else {
                w++;
            }
        }
    }

void sortColors(vector<int>& nums) {
        int sz = nums.size();
        int r = -1, w = 0, b = sz;
        //[0, r] is red, (r, w) is white, [b, sz-1] is black  
        while (w < b) {
            if (nums[w] == 0) {
                swap(nums[++r], nums[w++]);
            } else if (nums[w] == 2) {
                swap(nums[--b], nums[w]);
            } else {
                w++;
            }
        }
    }

follow up:

Given an array of n objects with k different colors (numbered from 1 to k), sort them so that objects of the same color are adjacent, with the colors in the order 1, 2, ... k.

Given colors=[3, 2, 2, 1, 4], k=4, your code should sort colors in-place to [1, 2, 2, 3, 4].

void sortColors2(vector<int> &colors, int k) {
        // write your code here
        int low = 1, high = k;  
        // (-1, left]           [right, colors.size())
        int left = -1, mid = 0, right = colors.size();
        while (low < high) {
            while (mid < right) {
                if (colors[mid] == low) {
                    swap(colors[mid++], colors[++left]);
                } else if (colors[mid] == high) {
                    swap(colors[mid], colors[--right]);
                } else {
                    mid++;
                }
            }
            mid = left + 1;
            low++;
            high--;
        }
    }

actually a bad implementation of quick sort, of which time complexity is O(n ^ 2)

class Solution{
public:
    /**
     * @param colors: A list of integer
     * @param k: An integer
     * @return: nothing
     */    
    void sortColors2(vector<int> &colors, int k) {
        // write your code here
        shuffle(colors);
        int sz = colors.size();
        quickSort(colors, 0, sz - 1);
    }
private:
    void shuffle(vector<int>& colors) {
        int sz = colors.size();
        for (int i = sz - 1; i > 0; i--) {
            int j = random() % (i + 1);
            swap(colors[i], colors[j]);
        }
    }
    
    int partition(vector<int>& colors, int start, int end) {
        for (int i = start; i < end; i++) {
            if (colors[i] < colors[end]) {
                swap(colors[start++], colors[i]);
            }
        }
        swap(colors[start], colors[end]);
        return start;
    }
    
    void quickSort(vector<int>& colors, int start, int end) {
        if (start >= end)   return;
        int p = partition(colors, start, end);
        quickSort(colors, start, p - 1);
        quickSort(colors, p + 1, end);
    }
};
⚠️ **GitHub.com Fallback** ⚠️