LeetCode 75. 颜色分类

75. 颜色分类

 

【计数排序】因为只有三种颜色，可以直接记录三种颜色各有多少，然后从0到1对原数组赋值即可。

class Solution {
    public void sortColors(int[] nums) {
        int[] cnt = new int[3];
        for (var x: nums) {
            cnt[x]++;
        }
        int i = 0, j = 0;
        while (j < nums.length) {
            while (cnt[i] == 0) {
                i++;
            }
            nums[j++] = i;
            cnt[i]--;
        }
    }
}

【双指针+两次扫描】用指针i枚举元素，指针j指向不为0的元素，每次i枚举到0的时候和指针j交换元素。第二次扫描的时候可以跳过前面的0，继续用这个方法来遍历。

class Solution {

    // 双指针+二次遍历

    public void sortColors(int[] nums) {
        int i = 0, j = 0, n = nums.length;
        for (i = 0; i < n; i++) {
            if (nums[i] == 0) {
                int t = nums[i];
                nums[i] = nums[j];
                nums[j] = t;
                j++;
            }
        }
        j = 0;
        while (j < n && nums[j] == 0) {
            j++;
        }
        for (i = j; i < n; i++) {
            if (nums[i] == 1) {
                int t = nums[i];
                nums[i] = nums[j];
                nums[j] = t;
                j++;
            }
        }
    }
}

【三指针+一次扫描】用j和k分别指向要交换成0和1的位置，i继续枚举所有元素。当i遇到1的时候和k处的元素交换，当i遇到0时和j处的元素交换，但是这样会产生一个问题就是被交换到后面的元素可能是1，中间如果隔了很多2，那么顺序就不对了，因此这里还要再做一个判断。

举个

2，0，2，1，1，0        i = j = k = 0

1.i=0的时候是2，不用管

2.i=1的时候是0，和j=0进行交换变成了 0，2，2，1，1，0，因为交换回来的是2不用管；j=1,k=1

3.i=2的时候是2，不用管 

4.i=3的时候是1，和k=1进行交换变成了0，1，2，2，1，0，k=2

5.i=4的时候是1，和k=2进行交换变成了0，1，1，2，2，0，k=3

6.i=5的时候是0，和j=1进行交换变成了0，0，1，2，2，1，因为交换回来是1，所以继续和k=3进行交换变成了0，0，1，1，2，2

class Solution {

    // 三指针+一次遍历 10:25 10:35

    public void sortColors(int[] nums) {
        int i = 0, j = 0, k = 0, n = nums.length;
        for (i = 0; i < n; i++) {
            if (nums[i] == 1) {
                int t = nums[i];
                nums[i] = nums[k];
                nums[k] = t;
                k++;
            } else if (nums[i] == 0) {
                int t = nums[i];
                nums[i] = nums[j];
                nums[j] = t;
                j++;
                if (k < j) k = j;
                if (nums[i] == 1) {
                    t = nums[i];
                    nums[i] = nums[k];
                    nums[k] = t;
                    k++;
                }
            }
        }
    }
}