LeetCode 75 Sort Colors

LeetCode 2021-07-05 11:41:26 2021-07-13 21:09:21 88 次浏览

题目分析

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.

离谱,速度排名这么低。

未经允许,禁止转载,本文源站链接:https://iamazing.cn/