Sort Colors

2/21/2018 update
nums[i]等于2的时候不+1是因为如果换回来的是0,则需要再检查一遍。循环满足条件是i <= r,因为最后一个数也需要检查。

思路:
3个指针,left: left左边为0, right: 右边为2, i:遍历数组的指针。代码如下:

 public class Solution {  
   /*  
    * @param nums: A list of integer which is 0, 1 or 2   
    * @return: nothing  
    */  
   public void sortColors(int[] nums) {  
     // write your code here  
     int left = 0, right = nums.length -1, i = 0;  
     while(i <= right) {  
       if(nums[i] == 0) {  
         swap(nums, i++, left++);  
       } else if(nums[i] == 1) {  
         i++;  
       } else  
       {  
         swap(nums, i, right--);  
       }  
     }  
   }  
   private void swap(int[] a, int i, int j) {  
     int tmp = a[i];  
     a[i] = a[j];  
     a[j] = tmp;  
  }  
 }  

为什么等于0时i++,等于2是不变。因为数组是从左到右遍历的,可以保证i的左边都是sorted order。

评论

此博客中的热门博文

776. Split BST

663. Equal Tree Partition

532. K-diff Pairs in an Array