Leetcode-075-颜色分类

思路：两次二分法查找

题目描述

• 给定一个包含红色、白色和蓝色，一共 n 个元素的数组，原地对它们进行排序，使得相同颜色的元素相邻，并按照红色、白色、蓝色顺序排列。
• 此题中，我们使用整数 0、 1 和 2 分别表示红色、白色和蓝色。

经典的荷兰旗问题

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

示例:

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

思想 ： 快速排序

一句话题解：做对这道题需要熟悉快速排序的 partition 过程。

我们在学习 快速排序 的时候知道，可以选择一个标定元素（称为 pivot ，一般而言随机选择），然后通过一次扫描，把数组分成三个部分：

• 第 1 部分严格小于 pivot 元素的值；
• 第 2 部分恰好等于 pivot 元素的值；
• 第 3 部分严格大于 pivot 元素的值。

第 2 部分元素就是排好序以后它们应该在的位置，接下来只需要递归处理第 1 部分和第 3 部分的元素。

经过一次扫描把整个数组分成 3个部分，正好符合当前问题的场景。写对这道题的方法是：把循环不变量的定义作为注释写出来，然后再编码。

设计循环不变量的原则

循环不变量：声明的变量在遍历的过程中需要保持定义不变。

说明：设计循环不变量的原则是 不重不漏。

len 是数组的长度；
变量 zero 是前两个子区间的分界点，一个是闭区间，另一个就必须是开区间；
变量 i 是循环变量，一般设置为开区间，表示 i 之前的元素是遍历过的；
two 是另一个分界线，我设计成闭区间。

如果循环不变量定义如下：

• 所有在子区间 [0, zero) 的元素都等于 0；
• 所有在子区间 [zero, i) 的元素都等于 1；
• 所有在子区间 [two, len - 1] 的元素都等于 2。

于是编码要解决以下三个问题：

• 变量初始化应该如何定义；
• 在遍历的时候，是先加减还是先交换；
• 什么时候循环终止。

处理这三个问题，完全看循环不变量的定义。

• 编码的时候，zero 和 two 初始化的值就应该保证上面的三个子区间全为空；
• 在遍历的过程中，「下标先加减再交换」、还是「先交换再加减」就看初始化的时候变量在哪里；
• 退出循环的条件也看上面定义的循环不变量，在 i == two 成立的时候，上面的三个子区间就正好 不重不漏 地覆盖了整个数组，并且给出的性质成立，题目的任务也就完成了。

class Solution {
    public void sortColors(int[] nums) {
        int len = nums.length;
        if(len < 2){
            return;
        }

        // all in [0, zero) = 0
        // all in [zero, i) = 1
        // all in [two, len - 1] = 2

        // 循环终止的条件的 i == two 那么循环可以继续等待的条件是 i < two
        // 为了保证初始化的时候[0,zero) 为空  , 设置 zero = 0；
        // 所以下面遍历到 0 的时候，先交换，再加
        int zero = 0;

        // 为了保证初始化的时候[two, len - 1] 为空 设置 two = len
        // 所以下面遍历到2的时候，先减 在交换
        int two = len;
        int i = 0;

        // 当 i == two 上面的三个子区间正好覆盖了全部数组
        // 因为 循环可以继续的条件是 i  < two

        while(i < two){
            if(nums[i] == 0){
                swap(nums,i,zero);
                zero++;
                i++;
            }else if(nums[i] == 1){
                i++;
            }else{
                two--;
                swap(nums,i,two);
            }
        }
    }

    private void swap(int[] nums,int index1,int index2){
        if(index1 == index2){
            return;
        }
        nums[index1] = nums[index1] ^ nums[index2];
        nums[index2] = nums[index1] ^ nums[index2];
        nums[index1] = nums[index1] ^ nums[index2];
    }
}

复杂度分析

• 时间复杂度：O(N)，这里 N是输入数组的长度；
• 空间复杂度：O(1)。

打赏