【力扣算法题】颜色排序

Posted on | In

75. Sort Colors

Given an array 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.

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

Note: You are not suppose to use the library's sort function for this problem.

Example:

Input: [2,0,2,1,1,0]
Output: [0,0,1,1,2,2]

方法一：搜索计数

时间复杂度：O(n) 两遍扫描

空间复杂度：O(1)

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
/*
* 计数统计法
*
* 思路：元素类型有限（0、1、2），统计每一种颜色的个数，然后再依次填入数组
*
* 时间复杂度 ： O(n) 两遍扫描数组
* 空间复杂度 ： O(1)
* */
public static void sortColors1(int[] nums) {
    int[] count = new int[3];
    // 遍历元素
    for (int num : nums) {
        // 对应元素次数加一
        count[num]++;
    }
    int index = 0;
    for (int i = 0; i < count[0]; i++) {
        nums[index++] = 0;
    }
    for (int i = 0; i < count[1]; i++) {
        nums[index++] = 1;
    }
    for (int i = 0; i < count[2]; i++) {
        nums[index++] = 2;
    }
}

方法二：多路搜索交换（三路快排思路）

时间复杂度：O(n) 一遍扫描

空间复杂度：O(1)

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
/*
* 三路快排( 多路快排 ) 交换元素
*
* 思路：三个指针（zero、i、two），[0,zero]区间都存放元素0，[zero+1,i-1]区间存储元素1，[two,n-1]区间存放元素2
* 移动指针 i , 寻找元素，判断是0、1、2，然后和 指针 zero 、two 位置元素进行互换
*
* 时间复杂度：O(n) 一遍扫描
* 空间复杂度：O(1)
* */
public static void sortColors2(int[] nums) {
    // 初始 [0,-1]表示初始没有任何元素区间
    int zero = -1;
    // 初始 [n,n-1] 同理 也是空区间
    int two = nums.length;
    int temp;
    // 初始化 i 指针 遍历数组 填充区间
    for (int i = 0; i < two; ) {
        if (nums[i] == 1)
            i++;
        else if (nums[i] == 2) {
            temp = nums[--two];
            nums[two] = nums[i];
            nums[i] = temp;
        } else {
            temp = nums[++zero];
            nums[zero] = nums[i];
            nums[i++] = temp;
        }
    }
}