Sort Colors, Leetcode 解题笔记

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.

click to show follow up.

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?

第一思路竟然不是follow up中给出的counting sort,自己鄙视自己一下。首先考虑的就是two pointer问题,从前往后扫,遇到不是0的就与后面的0交换位置,把0都找完然后再扫一遍找1。这个方法需要扫两遍,与follow up中的counting sort方法时间复杂度是一样的。其实稍作改动扫一遍就可以了,遇到0往前放,遇到2往后放。但是这种方法只适用于3种颜色,如果多于3种就不好使了。

public class Solution {
    public void sortColors(int[] A) {
        int red = 0;
        int blue = A.length-1;
 
        int i = red;
        while(i <= blue){
            if(A[i] == 0 && i > red){
                swap(A, i, red);
                red++;
                continue;
            }
            if(A[i] == 2){
                swap(A, i, blue);
                blue--;
                continue;
            }
            i++;
        }
    }
    public void swap(int[]A, int i, int j){
        int temp = A[i];
        A[i] = A[j];
        A[j] = temp;
    }
}
Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s