[leetcode] 75. 分类颜色(常数空间且只扫描一次算法)

我们直接按难度最高的要求做：你能想出一个仅使用常数空间的一趟扫描算法吗？

常数空间
只能扫描一趟。注意，是一趟，而不是O(n)

题中只会出现3个数字：0，1，2。换句话说，0肯定在最前面，2肯定都在后面，1都在中间

思路大概这样：

我们用双指针法，i从前往后扫，当num[i]!=0时，j从后往前扫，直到找到第一个非2的数。然后我们就需要分情况讨论了

当num[i]2 && num[j]0时，两数可以直接交换，i++然后继续

当num[i]1 && num[j]0时，两数交换，然后此时i继续往前扫，找下一个非0的数。找到后还要分情况讨论，找到的如果是2，那太好了，就可以把num[j]上的1替换掉了。

当num[i]2 && num[j]1时，balabala

。。。

总之，双指针法，如果找到了0或者2，那么其位置可以立即确定，直接替换到前面或者后面，替换的过程中呢，中间的1也就逐渐的确定位置了，当i>=j时，排序完成。整个算法只扫了一次数组,且只用的少量的空间

class Solution {

    public void sortColors(int[] nums) {

        int i = 0;

        int j = nums.length - 1;

        while (i < j) {

            while (i < j && nums[i] == 0) i++;

            if (i >= j) break;

            if (nums[i] == 1) {

                int k = i + 1;

                while (k < j && nums[k] == 1) {

                    k++;

                }

                if (nums[k] == 0) {

                    nums[i] = 0;

                    nums[k] = 1;

                    i++;

                } else if (k < j && nums[k] == 2) {

                    while (j > k && nums[j] == 2) {

                        j--;

                    }

                    if (nums[j] == 0) {

                        nums[j] = 2;

                        nums[i] = 0;

                        nums[k] = 1;

                        i++;

                    } else if (nums[j] == 1) {

                        nums[j] = 2;

                        nums[k] = 1;

                    }

                } else break;

            } else if (nums[i] == 2) {

                while (j > i && nums[j] == 2) {

                    j--;

                }

                if (nums[j] == 0) {

                    nums[i] = 0;

                    nums[j] = 2;

                    i++;

                } else if (nums[j] == 1) {

                    nums[i] = 1;

                    nums[j] = 2;

                }

            }

        }

    }

}

巴特西

[leetcode] 75. 分类颜色(常数空间且只扫描一次算法)

最新文章

热门文章