Noob
0%

Sort colors

发表于 更新于 分类于 ，

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.

https://leetcode.com/problems/sort-colors/

Counting sort

Iterator the array conounting the number of 0’s, 1’s, 2’s, then overwrite the array with total number of 0’s, 1’s and t2’s.

1
2
3
4
5
6
7
8
9
10
11
12
13
void sortColors(int A[], int n) {
    int num0 = 0, num1 = 0, num2 = 0;

    for(int i = 0; i < n; i++) {
        if (A[i] == 0) ++num0;
        else if (A[i] == 1) ++num1;
        else if (A[i] == 2) ++num2;
    }

    for(int i = 0; i < num0; ++i) A[i] = 0;
    for(int i = 0; i < num1; ++i) A[num0+i] = 1;
    for(int i = 0; i < num2; ++i) A[num0+num1+i] = 2;
}

Constant space solution

Using three variables i, j and k to record last indices of red, white and blue. 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public void sortColors(int[] nums) {
    if(nums == null || nums.length == 0) return;
    int r = -1, w = -1, b = -1;
    for(int i = 0; i < nums.length; ++i) {
        if(nums[i] == 0) {
            nums[++b] = 2;
            nums[++w] = 1;
            nums[++r] = 0;
        } else if(nums[i] == 1) {
            nums[++b] = 2;
            nums[++w] = 1;
        } else
            nums[++b] = 2;
    }
}