LeetCode 75. Sort Colors

75. Sort Colors（颜色分类）

链接

https://leetcode-cn.com/problems/sort-colors

题目

给定一个包含红色、白色和蓝色，一共 n 个元素的数组，原地对它们进行排序，使得相同颜色的元素相邻，并按照红色、白色、蓝色顺序排列。

此题中，我们使用整数 0、 1 和 2 分别表示红色、白色和蓝色。

注意:
不能使用代码库中的排序函数来解决这道题。

示例:

输入: [2,0,2,1,1,0]
输出: [0,0,1,1,2,2]
进阶：

一个直观的解决方案是使用计数排序的两趟扫描算法。
首先，迭代计算出0、1 和 2 元素的个数，然后按照0、1、2的排序，重写当前数组。
你能想出一个仅使用常数空间的一趟扫描算法吗？

思路

一道数组题目，解法多种。
说不让用代码库中的排序函数，那自己写一个应该不算违规吧23333.
只有三种数字，012，那么可以遍历统计每个数字的数量，之后直接更改。
也可以用三指针法，index012，一共三个变量，index0和1初始值是0，index2初始值是nums.length-1.遍历使用index1，发现那个数字为0，就和index0的数交换，为2就和index2的数交换，这里要注意，index2换过来的数还需要再判断一下。

代码

  public static void swap(int[] nums, int i, int j) {
  int temp = nums[i];
  nums[i] = nums[j];
  nums[j] = temp;
}

public void sortColors(int[] nums) {
  int index0 = 0, index1 = 0, index2 = nums.length - 1;
  while (index1 <= index2) {
    if (nums[index1] == 0) {
      swap(nums, index1, index0);
      index0++;
      index1++;
    } else if (nums[index1] == 2) {
      swap(nums, index1, index2);
      index2--;
    } else {
      index1++;
    }
  }
}