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进行遍历
  • 置换完之后是否还要对被置换到位置上面的值进行判断: 具体看comments
    • 如果当前值是0,置换完之后不需要对当前位置上的新元素进行判断,直接i++
    • 如果当前值是2,置换完之后仍然需要对当前位置上的新元素进行判断,所以需要在i++之前i–(或者其他随便什么)
  • 注意这里: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
//这里的位于i的0与位于p的元素交换了:因为i是从左到右扫描的,所以被置换到目前i的位置的值
一定是1或者0,不可能是2.因为p一定是<=i的.也就是i的左边一定都是0或者1,所以只要交换完毕
就可以直接跳过不用考虑了. 如果i是从右到左扫描的话,那么就刚好相反.当nums[i] == 0
置换完之后i不边,重新对置换之后的只进行判断.
            }else if (nums[i] == 2){
                swap(nums, i --, q --); //置换2之后,i不增加
//这里置换位于i处的2之后i不增加,因为要重新对被新置换到i上面的值再次进行判断.
//因为并不知道位于q上的值是什么,可能是1,0,也可能是还没有被扫描到的2.
                //如果q初始化为n的话,这里就是 -- q
            }}}

//另一个while loop的写法
 public void sortColors(int[] nums) {
 if(nums == null || nums.length == 0) return;
 int i = 0, j = nums.length - 1;
 for (int p = 0; p <= j; p ++){
//这里要先对num[p]==2先置换,再对num[p]==0置换.
//如果p是从后往前扫的话,那么就要反过来先对num[p] == 0置换,在对num[p] == 2置换.
 while(nums[p] == 2 && p < j){  swap(nums, p, j --);  }  while(nums[p] == 0 && p > i){
 swap(nums, p, i ++);
 } }  }

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: