LeetCode刷题之HOT100之颜色分类

下午好呀，大家！昨天估计是喝了假酒，现在没有胃口，喝酒真的没有任何好处。以后尽量避免此活动。今天几乎没睡觉，准备做完这题回宿舍，把电脑也带回去。

1、题目描述

2、逻辑分析

对颜色排序，要求是原地排序。以下是我想出来的代码

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

哈哈哈啊，秒了嘿嘿
Anyway，怎么解决呢？官方给出了单指针、双指针等方法。下面先来看看单指针：

• 对数组进行两次遍历。
• 在第一次遍历中，我们将数组中所有的 0 交换到数组的头部。在第二次遍历中，我们将数组中所有的 1 交换到头部的 0
  之后。此时，所有的 2 都出现在数组的尾部，这样我们就完成了排序。

那就直接代码演示

3、代码演示

public void sortColors(int[] nums) {
       int n = nums.length;
       int p = 0;
       for(int i = 0; i < n; i++){
        if(nums[i] == 0){
            int temp  = nums[i];
            nums[i] = nums[p];
            nums[p] = temp;
            p++;
        }
       }
       for(int i = p; i < n; i++){
        if(nums[i] == 1){
            int temp = nums[i];
            nums[i] = nums[p];
            nums[p] = temp;
            p++;
        }
       }
     }

在这里就不必注释了，简单明了。
时间复杂度：O(n)，空间复杂度：O(1)。
接下来看看双指针方法，算了，双指针也是乏善可陈，今天就先到这儿了，我得回去了。