75. Sort Colors

三刷 05/2022

Version #1 Bucket Sort

Time O(n)

Space O(k) -> k is count of colors

Runtime: 0 ms, faster than 100.00% of Java online submissions for Sort Colors.

Memory Usage: 43.3 MB, less than 5.72% of Java online submissions for Sort Colors.

class Solution {

    public void sortColors(int[] nums) {

        // bucket sort

        int[] cnt = new int[3];

        for (int num : nums) {

            cnt[num]++;

        }

        int pointer = 0;

        for (int i = 0; i < cnt.length; i++) {

            while (cnt[i] > 0) {

                nums[pointer] = i;

                cnt[i]--;

                pointer++;

            }

        }

    }

}

Version #2 Partition like quick sort

Time O(n)

Space O(1)

写了一个bug, 就是终止条件应该是 i <= right

注意left和right的定义是不包含已经sort好的最后一个element的

Runtime: 0 ms, faster than 100.00% of Java online submissions for Sort Colors.

Memory Usage: 40.5 MB, less than 97.04% of Java online submissions for Sort Colors.

class Solution {

    public void sortColors(int[] nums) {

        // Partition the array with 3 pointers

        //            i

        // ... left ... ... right

        // we need to ensure that all numbers on the left side of the left pointer are 0

        // all numbers on the right side of the right pointer are 2

        if (nums == null || nums.length == 0) {

            return;

        }

        //      l r

        //      i

        // [0,0,1,1,2,2]

        int left = 0, right = nums.length - 1;

        int i = 0;

        while (i <= right) {

            if (nums[i] == 0) {

                swap(nums, i, left);

                left++;

                i++;

            } else if (nums[i] == 2) {

                swap(nums, i, right);

                right--;

            } else {

                i++;

            }

        }

    }

    private void swap(int[] nums, int i, int j) {

        int temp = nums[i];

        nums[i] = nums[j];

        nums[j] = temp;

    }

}

二刷
Version #3 One pass Two Pointers
100.00 %
挡板问题 -> 分成 //  [0, i) [i, j)  unchecked    [k, len) 四个区域
要求在扫描的过程中这个定义永远是正确的
两个bug
1. j 的终止条件是 j < k,  而不是 j < length. 因为k以后的是check过的
2. j k swap之后 j 要--， 因为此时是把k 位置上未知的元素swap过来了，需要重新check一遍

class Solution {
    public void sortColors(int[] nums) {
        //  0 0 0  1  1  1 XXX  2  2  2
        //  [0, i) [i, j)       [k, len)
        int i = 0, j = 0, k = nums.length;
        while (j < k) {
            if (nums[j] == 0) {
                swap(nums, i, j);
                i++;
            } else if (nums[j] == 2) {
                k--;
                swap(nums, k, j);
                j--;
            }
            j++;
        }
       
    }
    private void swap(int[] nums, int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }
}


Version #2 Two pass count like bucket sort

100.00 %
一刷的解法也是two pass但是完全按照 bucket sort的方法算了累加之后的index
现在写的这种利用count[i]-- > 0 省略了算累计index的这一步
class Solution {
    public void sortColors(int[] nums) {
        int[] count = new int[3];
        for (int num : nums) {
            count[num]++;
        }
        int p = 0;
        for (int i = 0; i < count.length; i++) {
            while (count[i] > 0) {
                nums[p] = i;
                count[i]--;
                p++;
            }
        }
    }
}


一刷
Version #1 Bucket sort

64.04%

public class Solution {
    public void sortColors(int[] nums) {
        if (nums == null || nums.length == 0) return;
        int[] count = new int[3];
        for (int i = 0; i < nums.length; i++) {
            count[nums[i]] += 1;
        }
        for (int j = 1; j < count.length; j++) {
            count[j] = count[j - 1] + count[j];
        }
        // 0  1  2
        //[1, 3, 4]
        //curr = 0, 1, 2
        int index = 0;
        for (int curr = 0; curr < count.length; curr++) {
            while (index < count[curr]) {
                nums[index++] = curr;
            }
        }
    }
}