Description Link to heading

75.sort-colors

Solution Link to heading

Here, we need three pointers l, r, idx, l for 0, r for 2, idx for traversing.

When traversing:

  • if nums[idx] == 0,swap(nums[idx], nums[l]);, and idx++; l++
  • if nums[idx] == 1, idx++;
  • if nums[idx] == 2, swap(nums[idx], nums[r]);, and only r--, because new nums[idx] may be 0 or 1 or 2, so we need determine the value of nums[idx] again.
  • if swap(nums[idx], nums[l]);, new nums[idx] will be 0 only when idx == l, or nums[idx] == 1, so we can increase idx.

Code Link to heading 

class Solution {
  public:
    void sortColors(vector<int> &nums) {
        int tmp = 0, index = 0;
        int l = 0, r = nums.size() - 1;
        while (index <= r) {
            if (nums[index] == 0) {
                tmp = nums[l];
                nums[l++] = 0;
                nums[index++] = tmp;
            } else if (nums[index] == 2) {
                tmp = nums[r];
                nums[r--] = 2;
                nums[index] = tmp;
            } else
                index++;
        }
    }
};