计数排序变型

技术总结
LeetCode

context

75. Sort Colors

这是一道以计数排序为基本解法的题，而且最大值为2，比较好实现。

count sum

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution {
    public void sortColors(int[] nums) {
        int[] counts = new int[3];
        for(int num: nums) {
            counts[num]++;
        }
        
        for(int i = 0; i < nums.length; i++) {
            if(counts[0] > 0) {
                nums[i] = 0;
                counts[0]--;
                continue;
            }
            else if(counts[1] > 0) {
                nums[i] = 1;
                counts[1]--;
                continue;
            }else if(counts[2] > 0) {
                nums[i] = 2;
                counts[2]--;
                continue;
            }
        }
    }
}

改造的countsum

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
    public void sortColors(int[] nums) {
        int n0 = -1, n1 = -1, n2 = -1;//三个数的index
        for(int i = 0; i < nums.length; i++) {
            if(nums[i] == 0) {//当是0是三个数都往后写
                nums[++n2] = 2;
                nums[++n1] = 1;
                nums[++n0] = 0;
            }else if(nums[i] == 1) {
                nums[++n2] = 2;
                nums[++n1] = 1;
            }else{//当是二的时候，只要2往后写就可以
                nums[++n2] = 2;
            }
        }
    }
}

交换

由于只有0/1/2这三个数，将0从最前面开始放，2从最后面开始放。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
    public void sortColors(int[] nums) {
        int zeroIndex = 0, twoIndex = nums.length - 1;
        for(int i = 0; i <= twoIndex;) {
            if(nums[i] == 0) {
                nums[i] = nums[zeroIndex];
                nums[zeroIndex] = 0;
                i++;
                zeroIndex++;
            }else if(nums[i] == 2) {
                nums[i] = nums[twoIndex];
                nums[twoIndex] = 2;
                twoIndex--;
            }else
                i++;
        }
    }
}