GuilinDev

Lc0075

05 August 2008

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:

1
2

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

Follow up:

  • A rather straight forward solution is a two-pass algorithm using counting sort. First, iterate the array counting number of 0’s, 1’s, and 2’s, then overwrite array with total number of 0’s, then 1’s and followed by 2’s.
  • Could you come up with a one-pass algorithm using only constant space?

题意和分析

题目中说了如果两次扫描的做法，先计数，然后打印出来，利用一个三个元素的array或者HashMap或，然后再把打印即可。

如果想一次扫描就排好序，利用三路快排的思想，因为0，1，2分别代表one，two，three，最后需要排成012这样的顺序，那就用两个索引，把第一个索引指向头部(-1)，第二个索引指向尾部(nums.length())，然后遍历数组，如果遇到当前元素为0，则当前元素与第一个索引交换值，同时第一个索引往后移动一步；如果遇到2，则当前元素与第二个索引交换值，同时第二个索引往前移动一步；如果遇到1，继续遍历不作改变。

当然，三个指针也是可以的，都从0开始，遍历nums，如果等于2，只有第三个指针移动；如果等于1，第二个和第三个指针一起移动；如果等于0，三个指针都移动。

代码

三路快排思想，优先掌握

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 zero = 0, two = nums.length - 1;
        int index = 0;
        while (index <= two) {
            if (nums[index] == 0) {
                swap(nums, index, zero);
                index++;
                zero++;
            } else if (nums[index] == 2) {
                swap(nums, index, two);
                two--;
            } else {
                index++;
            }
        }
    }
    private void swap(int[] nums, int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }
}

计数排序的办法，先算出每个元素出现的次数，然后再填充回nums中，需要扫描两遍。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

class Solution {
    public void sortColors(int[] nums) {
        if (nums == null || nums.length == 0) {
            return;
        }
        //统计0，1，2各自出现的次数
        int[] counts = new int[3];
        for (int i = 0; i <= nums.length - 1; i++) {
            assert(nums[i] >= 0 && nums[i] <= 2);
            counts[nums[i]]++;
        }
        int index = 0;//from left to right in nums[],表示0，1各自的锚定点
        for (int i = 0; i <= counts.length - 1; i++){ // 0, 1, 2
            for (int j = index; j <= index + counts[i] - 1; j++) {
                nums[j] = i;
            }
            //填完0/1后移动锚定点
            index += counts[i];
        }
    }
}
This site is open source. Improve this page.