LeetCode 75 Sort Colors

    
        标签：
        
            LeetCode
        
    发布于：2021-07-05 11:41:26
    编辑于：2021-07-13 21:09:21
    浏览量：1097

题目分析

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

实际上就是一个特化情况（仅有三种值）下的原地排序问题。

无视条件直接排序

我们完全可以无视条件，直接用通用的 in-place 排序算法进行求解，如选择排序，插入排序。

我的三指针错误解法

81 / 87 test cases passed.

class Solution {
public:
    void sortColors(vector<int>& nums) {
        int l = 0, i = 0, j = nums.size()-1, r = nums.size()-1;
        while (i<=j) {           
            if (nums[l] == 0) {
                l++;
                i = l;
                continue;
            }
            if (nums[r] == 2) {
                r--;
                j = r;
                continue;
            }
            if (nums[l] != nums[r]) {
                swap(nums[l], nums[r]);
                if (nums[l] == 2 && nums[r] == 0) {
                    l++;
                    i = l;
                    r--;
                    j = r;                    
                }
                continue;
            }
            assert(nums[l] == 1);
            assert(nums[r] == 1);
            i++;
            j--;
            while (i<=j && (i!=l || j!=r)){
                switch(nums[i]) {
                    case 0:
                        swap(nums[i], nums[l]);
                        l++;
                        break;
                    case 2:
                        swap(nums[i], nums[r]);
                        r--;
                        break;
                }
                i++;
                switch(nums[j]) {
                    case 0:
                        swap(nums[j], nums[l]);
                        l++;
                        break;
                    case 2:
                        swap(nums[j], nums[r]);
                        r--;
                        break;
                }
                j--;
            }
        }
    }
};

搞的太复杂了。

高赞 one pass 三指针解法

https://leetcode.com/problems/sort-colors/discuss/26481/Python-O(n)-1-pass-in-place-solution-with-explanation

class Solution {
public:
    void sortColors(vector<int>& nums) {
        int c0 = 0, c1 = 0, c2 = nums.size() - 1;
        while (c1 <= c2) {
            if (nums[c1] == 0) {
                swap(nums[c0], nums[c1]);
                c0++;
                c1++;
            } else if (nums[c1] == 1) {
                c1++;
            } else {
                swap(nums[c1],nums[c2]);
                c2--;
            }
        }
    }
};

三个指针 c0，c1 和 c2 分别指向值为 0，1，2 的元素。

我们确保 c0 的左边的值均为 0，c2 的右边的值均为 2。

初始时，c0 在最左边，c2 在最右边。

c1 可以在最左边，此时当 nums[c1] 为 0 时，在交换 c0 和 c1 所处位置的值后，我们必须同时更新 c0 和 c1，而不能仅更新 c0，否则的话会出现 c1 小于 c0 的情况。

我们必须避免这种情况，否则将出现把已排序的部分换出来的情况，而我们是不能动已排序好的部分的。

基于高赞解法的改进方法

基于此，我改了一下：

class Solution {
public:
    void sortColors(vector<int>& nums) {
        int c0 = 0, c1 = 0, c2 = nums.size() - 1;
        while (c1 <= c2) {
            if (nums[c1] == 0) {
                swap(nums[c0], nums[c1]);
                c0++;
                c1 = max(c1, c0+1);
            } else if (nums[c1] == 1) {
                c1++;
            } else {
                swap(nums[c1],nums[c2]);
                c2--;
            }
        }
    }
};

WA 了，不过 86 / 87 test cases passed，此时输入为 [0,2,1]，算法输出却是 [0,2,1]。

emmmm，问题在于 c1 = max(c1, c0+1); 可能会导致出现 c1 = c2 的情况。实际上没必要 + 1 哈，只需要确保 c1 不在 c0 的左边即 c1 >= c0 即可。

class Solution {
public:
    void sortColors(vector<int>& nums) {
        int c0 = 0, c1 = 0, c2 = nums.size() - 1;
        while (c1 <= c2) {
            if (nums[c1] == 0) {
                swap(nums[c0], nums[c1]);
                c0++;
                c1 = max(c1, c0);
            } else if (nums[c1] == 1) {
                c1++;
            } else {
                swap(nums[c1],nums[c2]);
                c2--;
            }
        }
    }
};

Runtime: 4 ms, faster than 48.12% of C++ online submissions for Sort Colors.

离谱，速度排名这么低。

Links: leetcode-75-sort-colors