75. Sort Colors - Medium

前往題目

之前寫的文章

想法

• 數0、1、2各有幾個，然後填回原本的陣列

思路

上述想法可行，但以下方法更快速

1. 三個指針，左中右
2. 中間指針遇到2就與右指針數值交換，並且左移右指針
3. 中間指針遇到0就與左指針數值交換，並且右移左指針與中間指針，因為初始狀態l和mid都是0，不移動會出現l大於mid的狀況

Code

直覺做法，紀錄個數

class Solution {
    public void sortColors(int[] nums) {
        int zeros = 0;
        int ones = 0;
        int twos = 0;

        for (int num : nums) {
            switch(num) {
                case 0:
                    ++zeros;
                    break;
                case 1:
                    ++ones;
                    break;
                case 2:
                    ++twos;
                    break;
            }
        }

        for (int i = 0; i < nums.length; ++i) {
            if (zeros > 0) {
                nums[i] = 0;
                --zeros;
            } else if (ones > 0) {
                nums[i] = 1;
                --ones;
            } else {
                nums[i] = 2;
                --twos;
            }
        }
        
    }
}

3 pointers

class Solution {
    public void sortColors(int[] nums) {
        int l = 0, mid = 0, r = nums.length - 1;

        while (mid <= r) {
            // 遇到2，與r交換
            if (nums[mid] == 2) {
                int temp = nums[r];
                nums[r] = 2;
                nums[mid] = temp;
                --r;
              // 遇到0，與l交換  
            } else if (nums[mid] == 0) {
                int temp = nums[l];
                nums[l] = 0;
                nums[mid] = temp;
                // 一起移動
                ++l;
                ++mid;
            } else {
                ++mid;
            }
        }
    }
}

2024/06/24

• 小bug，遇到2的時候中指針不用動，不然可能會跳過0