LeetCode之75. 颜色分类

问题描述

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

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

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

示例:

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

进阶：

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

三向切分

这道题在边界条件上花费了很多时间。这个算法太容易写错了。注意与《算法》第四版189页代码的不同，书上v选取了第一个元素，所以，curr初始值为lt+1，任何时刻nums[lt]都为v，因此与nums[lt]交换后curr可向前移动。

class Solution {
private:
    void exch(vector<int>& nums, int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }
public:
    void sortColors(vector<int>& nums) {
        int v = 1;
        int lt = 0;  // nums[0..lt-1] < 1, nums[lt] <= 1, 因此与nums[lt]交换后curr可向前移动
        int gt = nums.size()-1;
        int curr = lt;	// 开始与lt必须指向相同位置，保证不漏排任何一个元素
        while (curr <= gt) {
            int c = nums[curr] - v;
            if (c > 0) exch(nums, curr, gt--);  // 这里curr不能加加，否则就漏排与curr交换了的nums[gt]
            else if (c < 0) exch(nums, curr++, lt++);  // 这里curr一定要加加，否则循环可能前进不动
            else curr++;
        }
    }
};