leetcode解题: Sort Colors (75)

发表于 | 分类于

Given an array with n objects colored red, white or blue, sort them 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.

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 an one-pass algorithm using only constant space?

解法1： Bucket sort/counting sort, O(N) Time with two passes

Bucket sort, 统计0,1,2的个数然后再逐个写入
C++

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
class Solution {
public:
    void sortColors(vector<int>& nums) {
        // bucket sort
        int red = 0, white = 0, blue = 0;
        for (int i = 0; i < nums.size(); ++i) {
            if (nums[i] == 0) {
                red++;
            } else if (nums[i] == 1) {
                white++;
            } else {
                blue++;
            }
        }
        int i = 0;
        for (int j = 1; j <= red; j++) {
            nums[i++] = 0;
        }
        for(int j = 1; j <= white; j++) {
            nums[i++] = 1;
        }
        for (int j = 1; j <= blue; j++) {
            nums[i++] = 2;
        }
    }
};

Java

1

解法2： One pass O(N)

类似于双指针的思路,这里用了一个low记录0的位置,用了一个high记录2的位置,然后从左往右扫描. 如果是0或者2就知道该插入在什么地方,如果是1那么就往前移动.
C++

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
class Solution {
public:
    void sortColors(vector<int>& nums) {
        if (nums.size() <= 1) {
            return;
        }
        int low = 0, high = nums.size() -1;
        int mid = 0;
        while (mid < nums.size() && mid <= high) {
            if (nums[mid] == 0) {
                swap(nums, low, mid);
                ++low;
                ++mid;
            } else if (nums[mid] == 2) {
                swap(nums, high, mid);
                --high;
            } else {
                ++mid;
            }
        }
        return;
    }
    void swap(vector<int>& nums, int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] =temp;
    }
};

###解法3: One pass O(N) ###
用两个指针记录zero和one插入的位置。
对于每一个新数字，先插入最大的数字。因为如果是其他数字的话在之后的操作中会被覆盖。
然后从大到小的判断当前数字为哪一个。如果是1那么只移动one的位置并插入。
如果是zero，那么需要先移动one并且赋值，然后移动zero再赋值。如果zero插入的位置原本是一个1，那么被覆盖的1就被one的指针找回了。
Java

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
public class Solution {
    public void sortColors(int[] nums) {
        int zero = -1;
        int one = -1;
        for (int k = 0; k < nums.length; ++k) {
            int v = nums[k];
            nums[k] = 2;    // no matter what, set this to 2
            if (v == 0) {
                nums[++one] = 1;
                nums[++zero] = 0;
            } else if (v == 1) {
                nums[++one] = 1;    // advance one
            }
        }
        return;
    }
}