leetcode 75 Sorted Colors

两种解法

1）记录0和1的个数

然后按照记录的个数将0和1重新放入原数组，剩下的补2

2）双指针left,right

left表示0~left-1都为0，即i之前都为0

right表示right+1~nums.length都为2，即j之后都为2

遍历原数组

　　a)遇到为0的就把当前nums[i]与nums[left]交换

　　b)遇到为2的就交换nums[i]&nums[right]，注意，写代码的时候要考虑交换过来的nums[right]有可能是2，如果i正常迭代变成i+1，漏掉了nums[right]为2的情况，所以我们这里i要减1

那么为什么前面a)不需要i减一呢？因为按照我们对left的定义，nums[left]不可能为0

 class Solution {

     public void sortColors(int[] nums) {

         int len = nums.length;

         int index=0, i=0, j=len-1;

         while(index <= j){

             if(nums[index] == 0){

                 nums[index] = nums[i];

                 nums[i++] = 0;

             }

             if(nums[index] == 2){

                 nums[index] = nums[j];

                 nums[j--] = 2;

                 index--;

             }

             index++;

         }

     }

 }

巴特西

leetcode 75 Sorted Colors

最新文章

热门文章