LeetCode 75. Color classification

75. Color classification

 

【 Count sorting 】 Because there are only three colors , It can directly record the number of the three colors , And then from 0 To 1 Assign a value to the original array .

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]--;
        }
    }
}

【 Double pointer + Two scans 】 With a pointer i Enumeration elements , The pointer j Point not to 0 The elements of , Every time i Enumerate to 0 Time and pointer j Exchange elements . You can skip the previous one during the second scan 0, Continue to use this method to traverse .

class Solution {

    //  Double pointer + Second traversal 

    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++;
            }
        }
    }
}

【 Three pointers + A scan 】 use j and k Respectively point to exchange into 0 and 1 The location of ,i Continue enumerating all elements . When i encounter 1 When and k Element exchange at , When i encounter 0 Time and j Element exchange at , But this will cause a problem that the elements exchanged to the back may be 1, If there is a lot of separation in the middle 2, Then the order is wrong , So here is another judgment .

Take up a

2,0,2,1,1,0        i = j = k = 0

1.i=0 The time is 2, Never mind

2.i=1 The time is 0, and j=0 Exchange becomes 0,2,2,1,1,0, Because the exchange back is 2 Never mind ;j=1,k=1

3.i=2 The time is 2, Never mind  

4.i=3 The time is 1, and k=1 Exchange becomes 0,1,2,2,1,0,k=2

5.i=4 The time is 1, and k=2 Exchange becomes 0,1,1,2,2,0,k=3

6.i=5 The time is 0, and j=1 Exchange becomes 0,0,1,2,2,1, Because the exchange back is 1, So continue with k=3 Exchange becomes 0,0,1,1,2,2

class Solution {

    //  Three pointers + One traverse  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++;
                }
            }
        }
    }
}