leetcode 75 Sort Colors
z
 2018-03-13 11:31:54  

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.

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
class Solution {
    public void sortColors(int[] nums) {
        int sum = 0;
        int blue = 0;
        int red = 0;
        int white = 0;
        for(int i=0; i<nums.length; i++){
            sum += nums[i];
            if(nums[i] == 2){
                blue += 1;
            }
        }
        white = sum - blue*2;
        red = nums.length - blue - white;
        int i = 0;
        while(i<nums.length){
            if(i<red){
                nums[i] = 0;
            }
            else if(i<red + white){
                nums[i] = 1;
            }
            else{
                nums[i] = 2;
            }
            i ++;
        }
    }
}
  • 数出和是多少，2有多少个，从而计算出1有多少个，0有多少个，重新构建nums即可
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
    public void sortColors(int[] nums) {
        int zero = 0;
        int two = nums.length-1;
        for(int i=0; i<=two; i++){
            if(nums[i] == 0){
                swap(nums, i, zero);
                zero ++;
            }
            else if(nums[i] == 2){
                swap(nums, i, two);
                two --;
                i --;
            }
        }
    }
    public void swap(int[] nums, int i, int j){
        int t = nums[i];
        nums[i] = nums[j];
        nums[j] = t;
    }
}
  • zero指向第一个应该放0的位置
  • two指向第一个放2的位置
  • i从0到two，如果为0，和zero兑换位置，如果为2，和two兑换位置，值得注意的是缓过来的需要再次比较，导致i需要–。
    • 为什么zero置换后不需要i–？因为换过来的必然是1.

python:

1