力扣75——颜色分类

这道题主要在于空间复杂度的优化，利用指针，可以完成这一点。

原题

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

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

注意:

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

示例:

1 2	输入: [2,0,2,1,1,0] 输出: [0,0,1,1,2,2]

进阶：

1
2
3

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

原题url：https://leetcode-cn.com/problems/sort-colors/

解题

两趟扫描

我当时想到的第一种想法就是排序，后来感觉没有必要，因为只有3种元素，我完全就可以按照进阶提示中的第一条，先扫描统计出各元素个数，然后第二遍扫描时，直接进行赋值。

让我们直接来看代码：

class Solution {
    public void sortColors(int[] nums) {
        // 记录0,1,2的个数
        int num0 = 0, num1 = 0, num2 = 0;
        // 计算各个数字出现的次数
        for (int i : nums) {
            switch(i) {
                case 0:
                    num0++;
                    break;
                case 1:
                    num1++;
                    break;
                case 2:
                    num2++;
                    break;
            }
        }
        // 重新赋值
        for (int i = 0; i < nums.length; i++) {
            if (i < num0) {
                nums[i] = 0;
            } else if (i < num0 + num1) {
                nums[i] = 1;
            } else {
                nums[i] = 2;
            }
        }
    }
}

提交OK，执行用时：0 ms，内存消耗：35.2 MB。是否还可以优化呢？

优化

参考进阶提示中的第二条，上面的方法使用了常数空间，但一遍扫描该如何做到呢？

我其实并没有想出来，参考了别人的解法：利用三个指针进行一次遍历并交换。

具体来说，就是增加一个当前指针current（从下标0开始）、一个指向数字0区间的末尾指针p0（从下标0开始）、一个指向数字2区间的开始指针p2（从下标 nums.length - 1）。下标0 到下标 p0 之间存放数字0，下标 p0 到 p2 之间存放数字1，下标 p2 到下标 (nums.length - 1) 之间存放数字2。current 指针从下标0开始遍历，如果值为0，则和 p0 交换，如果值为2，则和 p2 交换。

让我们来看看代码：

class Solution {
    public void sortColors(int[] nums) {
        // 利用3个指针current、p0、p2
        int current = 0, p0 = 0, p2 = nums.length - 1;
        while (current <= p2) {
                    // 如果当前值为1，current指针往后移动
            if (nums[current] == 1) {
                current++;
                continue;
            }
                        
            // 如果当前值为0，则和 p0 交换，p0指针往后移动
            if (nums[current] == 0) {
                nums[current] = nums[p0];
                nums[p0] = 0;
                // 因为p0一开始和current相同
                if (p0 == current) {
                    current++;
                }
                p0++;
                continue;
            }

            // 如果当前值为2，则和 p2 交换，p2指针往前移动
            if (nums[current] == 2) {
                nums[current] = nums[p2];
                nums[p2] = 2;
                p2--;
                continue;
            }
        }
    }
}