（LeetCodeHot100）75. 颜色分类——sort-colors

75. 颜色分类——sort-colors

给定一个包含红色、白色和蓝色、共 n 个元素的数组 nums ，原地 对它们进行排序，使得相同颜色的元素相邻，并按照红色、白色、蓝色顺序排列。

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

必须在不使用库内置的 sort 函数的情况下解决这个问题。

示例 1：

1
2
输入：nums = [2,0,2,1,1,0]
输出：[0,0,1,1,2,2]

示例 2：

1
2
输入：nums = [2,0,1]
输出：[0,1,2]

提示：

  • n == nums.length
  • 1 <= n <= 300
  • nums[i] 为 0、1 或 2

进阶：

  • 你能想出一个仅使用常数空间的一趟扫描算法吗？

我的「不符合题目要求」答案：

  • 居然过了，但是时间复杂度太高→3ms|击败2.64%（而且不符合要求）
1
2
3
4
5
class Solution {
    public void sortColors(int[] nums) {
        Arrays.sort(nums);
    }
}

我的冒泡排序答案：

  • 显然肯定不是官方想要的答案：时间复杂度太高→2ms|击败4.53%（居然比sort还高）
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
    public void sortColors(int[] nums) {
        boolean flag = false;
        int n = nums.length;
        for (int i = 0; i < n - 1 && !flag; i++) {
            flag = true;
            for (int j = 0; j < n - i - 1; j++) {
                if (nums[j] > nums[j + 1]) {
                    int temp = nums[j];
                    nums[j] = nums[j + 1];
                    nums[j + 1] = temp;
                    flag = false;
                }
            }
        }
    }
}

我的快速排序答案：

  • 0ms|击败100.00%
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
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
class Solution {
    public void sortColors(int[] nums) {
        quickSort(nums, 0, nums.length-1);
    }
    private void quickSort(int [] nums, int left, int right) {
        // 临界条件
        if (left >= right) {
            return;
        }
        int index = Partition(nums, left, right);
        quickSort(nums, left, index-1);
        quickSort(nums, index+1, right);
    }
    // 用于得到基准的下标的，Partition意思就是分割
    private int Partition(int[] nums, int left, int right) {
        // 将第一个数作为基准
        int base = nums[left];
        // 把基准的值作为标准，分为小于基准和大于基准的
        while (left < right) {
            // 从right开始向左找到比基准小或等于的数
            while (left < right && nums[right] >= base) {
                right--;
            }
            // 将两个数换位置
            int temp = nums[left];
            nums[left] = nums[right];
            nums[right] = temp;

            // 从left开始向右找比基准大或等于的数
            while (left < right && nums[left] <= base) {
                left++;
            }
            // 将两个数换位置
            temp = nums[left];
            nums[left] = nums[right];
            nums[right] = temp;
        }
        // 此时基准就是left==right的位置了（因为左边没有比base大的，右边没有比base小的了）
        return left;
    }
}