LeetCode每日一题： 颜色分类

第一种解法，排序法，将数组升序排序一遍即可

• 代码

class Solution {
public void sortColors(int[] nums) {
  Arrays.sort(nums);
}
}

第二种解法，指针法

• 用三个指针l、r、index分别表示0的右边界，2的左边界，当前的数据下标

• 当nums[index] == 0,将其与nums[l]互换

• 当nums[index] == 2,将其与nums[r]互换

• 时间复杂度：O(N) 空间复杂度：O(1)

• 代码实现：

class Solution {
public void sortColors(int[] nums) {
  int l = 0;
  int r = nums.length-1;
  int index = 0;
  int temp;
  while(index <= r){
     if(nums[l] == 0){
         index++;
         l++;
         continue;
     }
     if(nums[index] == 0 && index != l){
        temp = nums[index];
        nums[index++] = nums[l];
        nums[l++] = temp;
     }else if(nums[index] == 2){
        temp = nums[index];
        nums[index] = nums[r];
        nums[r--] = temp;
     }else{
         index++;
     }
  }
}
}