【LeetCode】No.75. Sort Colors -- Java Version

题目链接：https://leetcode.com/problems/sort-colors/

1. 题目介绍（Sort Colors）

Given an array nums with n objects colored red, white, or blue, sort them in-place so that objects of the same color are adjacent, with the colors in the order red, white, and blue.

【Translate】： 给定一个数组nums，其中有n个红色、白色或蓝色的对象，对它们进行排序，使相同颜色的对象相邻，颜色按红、白、蓝的顺序排列。

We will use the integers 0, 1, and 2 to represent the color red, white, and blue, respectively.

【Translate】： 我们将使用整数0、1和2分别表示红色、白色和蓝色。

You must solve this problem without using the library’s sort function.

【Translate】： 您必须在不使用库的排序函数的情况下解决这个问题。

【测试用例】：

【条件约束】：

【跟踪】：

【Translate】： 你能想出一个只使用恒定额外空间的单遍算法吗?

2. 题解

2.1 内置排序函数

虽然题目说了不让用内置的排序函数，但是咱就是想看看用了的效果。

class Solution {
    public void sortColors(int[] nums) {
        Arrays.sort(nums);
        
    }
}
1
2
3
4
5
6

轻轻松松，但是速度是真不行。

2.2 左右开工的1-pass

原题解来自于young_stone的Java solution, both 2-pass and 1-pass。

该题解的思想类似于快排中的三路排序。

题目很自然的将整个数组分为3个区域，0，1，2，而且对顺序也早就做好了规定。我们定义左右变量，来指示区域的变化，如果当前元素为0，那么就与左元素进行交换，并让左元素为0，后移一位；如果当前元素为2，那么就与右元素交换，并让右元素为2，向左前进一位的同时，要让指示当前位置的索引index也向左前进一位，这是因为前面让元素发送了交换，未检索的右元素被交换到了当前索引的位置，所以我们要回退一位，去检索这个右元素。

class Solution {
    public void sortColors(int[] nums) {
        int l = 0, r = nums.length-1, index = 0;
        
        while (index <= r){
            if (nums[index] == 0){
                nums[index] = nums[l];
                nums[l] = 0;
                l++;
            }
            
            if(nums[index] == 2){
                nums[index] = nums[r];
                nums[r] = 2;
                r--;
                index--;
            }
            index++;
        }
            
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

2.3 统计计数的2-Pass

原题解来自于young_stone的Java solution, both 2-pass and 1-pass。

该题解采用了两次遍历，一次用来计数，第二次则根据第一次的计数来重新赋值。

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

3. 参考资料

[1] java sort排序函数 | CSDN
[2] 三路快排 3-way | CSDN
[3] 快速排序及其优化超详细解答+代码（真正理解）| 知乎