75. 颜色分类

给定一个包含红色、白色和蓝色、共 n 个元素的数组 nums ，原地对它们进行排序，使得相同颜色的元素相邻，并按照红色、白色、蓝色顺序排列。
我们使用整数 0、 1 和 2 分别表示红色、白色和蓝色。
必须在不使用库的sort函数的情况下解决这个问题。

示例 1：
输入：nums = [2,0,2,1,1,0] 输出：[0,0,1,1,2,2]
示例 2：
输入：nums = [2,0,1] 输出：[0,1,2]

提示：

  • n == nums.length
  • 1 <= n <= 300
  • nums[i] 为 0、1 或 2

进阶：

  • 你可以不使用代码库中的排序函数来解决这道题吗？
  • 你能想出一个仅使用常数空间的一趟扫描算法吗？

思路：
三指针即可

  1. class Solution {
  2.     public void sortColors(int[] nums) {
  3.         int n = nums.length;
  4.         for (int i = 0, j = 0, k = n - 1; i <= k; ) {
  5.             if (nums[i] == 0) {
  6.                 swap(nums, i, j);
  7.                 i++;
  8.                 j++;
  9.             } else if (nums[i] == 2) {
  10.                 swap(nums, i, k);
  11.                 k--;
  12.             } else {
  13.                 i++;
  14.             }
  15.         }
  16.     }
  17.     void swap(int[] a, int i, int j) {
  18.        int t = a[i];
  19.         a[i] = a[j];
  20.         a[j] = t;
  21.     }
  22. }