LC.P75[颜色分类]

方法一：哈希表

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
    public void sortColors(int[] nums) {
        Map<Integer, Integer> map = new HashMap<>();
        for (int num : nums) map.merge(num, 1, Integer::sum);
        int i = 0;
        for (int key : map.keySet()) {
            int cnt = map.get(key);
            while (cnt-- > 0) {
                nums[i++] = key;
            }
        }
    }
}
  • 时间复杂度：$O(n)$
  • 空间复杂度：$O(n)$

方法二：双指针

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
    public void sortColors(int[] nums) {
        int n = nums.length;
        int c0 = 0, c2 = n - 1;
        for (int c1 = 0; c1 <= c2; ++c1) {
            while (c1 <= c2 && nums[c1] == 2) {
                // 交换完成后 nums[c1] 仍有可能为 2，因此需继续交换直到 nums[c1] 不为 2
                swap(nums, c1, c2);
                --c2;
            }
            if (nums[c1] == 0) {
                swap(nums, c1, c0);
                ++c0;
            }
        }
    }

    private void swap(int[] nums, int a, int b) {
        int temp = nums[a];
        nums[a] = nums[b];
        nums[b] = temp;
    }
}
  • 时间复杂度：$O(n)$
  • 空间复杂度：$O(1)$