Sort Colors I II

Leave a comment

August 20, 2016 by oneOokay

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.


二刷的结果就是首先想到了最优的解决方法:两个pivot,把0都移到左边,2都移到右边,1留在中间.但是没有写通.

  • 一个p指针来指:0的最后一位;一个q指针来指:2的第一位.初始化p = -1; q = n;
    • 或者p指针来指非0的第一位;q:非2的最后一位; 初始化p=0; q = n-1;
  • 如此想有两个移动之后,其实还需要一个i来不断移动对nums进行遍历
  • 注意这里:i的范围并不是从[0,nums.length – 1]而是从[0,q)如果q是2的第一位;[0,q]如果q是非2的最后一位.
public void sortColors(int[] nums) {
        if (nums == null || nums.length <= 1) return;
        int n = nums.length;
        int p = 0;
        int q = n - 1;
        for (int i = 0; i <= q; i ++){//如果q初始化为n的话,这里就是i<q
            if (nums[i] == 0){
                swap(nums, i, p ++);//如果p初始化为-1的话,这里就是 ++ p
            }else if (nums[i] == 2){
                swap(nums, i --, q --); //置换2之后,i不增加
                //如果q初始化为n的话,这里就是 -- q
            }
        }
    }

Sort colors II:

给定一个有n个对象(包括k种不同的颜色,并按照1到k进行编号)的数组,将对象进行分类使相同颜色的对象相邻,并按照1,2,…k的顺序进行排序。


 

有四种方法…

 

count sort:扫一遍知道每个颜色多少个;扫第二遍正确的放置颜色

2. 参考sort colors 的解法:http://www.jiuzhang.com/solutions/sort-colors/

利用两个指针。首先找出min和max,这样每次loop排列好头尾两个颜色,接着排其他剩下的颜色。。。http://www.jiuzhang.com/solutions/sort-colors-ii/

那么来复习一下quicksort吧

public void sortColors2(int[] colors, int k) {
// write your code here
quickSort(colors, 0, colors.length – 1);
}

public void quickSort(int[] A, int start, int end) {
if(start >= end) { //end 的条件
return;
}
int pivot = A[ (start + end) / 2]; //pivot是这个值,而不是这个index
int left = start;
int right = end;
while(left <= right) {
while (left <= right && A[left] < pivot) {
left ++;
}
while (left <= right && A[right] > pivot) {
right –;
}

if(left <= right){ //left 和 right 有变动,所以仍需要进行判断
int temp = A[left];
A[left] = A[right];
A[right] = temp;
left ++;
right –;
}
}
quickSort(A, start, right);
quickSort(A, left, end);
}

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

%d bloggers like this: