本文概览本文讲解颜色分类荷兰国旗问题只有 0、1、2 三个值0 要排到最前面、2 要排到最后面中间剩下的自然是 1方法一是统计个数后重写方法二用左右两个指针各守一端一边遍历一边把 0 往左扔、2 往右扔只需一遍扫描一、题目二、题目分析1. 题目要求给定一个包含红色、白色和蓝色、共n个元素的数组nums原地对它们进行排序使得相同颜色的元素相邻并按照红色、白色、蓝色顺序排列。用整数0、1和2分别表示红色、白色和蓝色。必须在不使用库内置的sort函数的情况下解决这个问题。示例 1nums [2, 0, 2, 1, 1, 0]→[0, 0, 1, 1, 2, 2]示例 2nums [2, 0, 1]→[0, 1, 2]2. 怎么想这题题目说得很死数组里只有0、1、2三种值最后要排成所有 0 在前面、所有 1 在中间、所有 2 在后面。最直接的做法是先数再填扫一遍统计出 0、1、2 各有多少个然后照着个数把数组从头到尾重写一遍。思路没问题但要扫两遍数组。还能不能再省注意这里只有三个值而且规矩特别简单0的归宿是最前面2的归宿是最后面1夹在中间——也就是说只要把 0 和 2 都送对了地方剩下的位置自然全是 1压根不用管。那就可以在遍历的过程中边看边归位遇到 0 就往数组头部扔遇到 2 就往数组尾部扔。既然要往两端扔就得有两个指针分别记住头部扔到哪了、尾部扔到哪了。这就是双指针的思路一遍扫描就能排好。3. 需要解决哪几个问题问题一两个指针各自指向哪里、分别代表什么含义问题二遇到 0 或 2 时需要交换交换之后两个指针和遍历下标分别怎么移动问题三最容易错的细节为什么遇到 0 时遍历下标要往后走一格遇到 2 时却要停在原地再看一次三、方法一统计个数后重写两遍遍历1. 思路概览publicvoidsortColors(int[]nums){intcount00,count10,count20;// 第一遍数出各有多少个for(intnum:nums){if(num0)count0;elseif(num1)count1;elsecount2;}// 第二遍按个数把数组重新填满intidx0;for(intk0;kcount0;k)nums[idx]0;for(intk0;kcount1;k)nums[idx]1;for(intk0;kcount2;k)nums[idx]2;}思路简要说明第一遍统计数出 0、1、2 各有多少个第二遍填充按 0、1、2 的个数依次覆盖回数组时间复杂度 O(n)空间 O(1)只用三个计数器缺点要扫两遍数组2. 思路详解这个方法的逻辑和桶排序是一回事既然知道了每种值该占多少格直接按格子填就行了。以[2, 0, 2, 1, 1, 0]为例第一遍数完count0 2, count1 2, count2 2 第二遍填充前 2 格填 0 → [0, 0, _, _, _, _] 接着 2 格填 1 → [0, 0, 1, 1, _, _] 最后 2 格填 2 → [0, 0, 1, 1, 2, 2] ✓简单可靠代价是要遍历两遍。既然一趟就能解决就值得往下想。3. 复杂度分析时间复杂度 O(n)两遍线性扫描。空间复杂度 O(1)三个计数器。四、能不能一遍扫完回顾一下刚才那个观察0 的归宿是数组最左边2 的归宿是最右边而 1 只要站在中间就行。既然两个极端值各有明确的目的地那就可以一边遍历一边送它们回家遇到0把它和当前最左边还没确定的位置交换——这样 0 就落到该去的地方那个位置可以划进0 区了遇到2把它和当前最右边还没确定的位置交换——2 就落到尾部那个位置划进2 区遇到1先别动它让它在原地等着等 0 和 2 都归位它自然就落在中间了。于是需要两个指针一个盯左、一个盯右分别记录0 区和2 区已经推进到哪儿。下面是具体怎么落地。五、方法二双指针三路分区一遍遍历1. 思路概览publicvoidsortColors(int[]nums){intleft0;// 0 区的下一个空位intrightnums.length-1;// 2 区的上一个空位inti0;// 当前考察的位置while(iright){if(nums[i]0){// 把 0 换到左边界inttempnums[i];nums[i]nums[left];nums[left]temp;left;i;}elseif(nums[i]2){// 把 2 换到右边界inttempnums[i];nums[i]nums[right];nums[right]temp;right--;}else{// 是 1留在原地继续往后看i;}}}思路简要说明left[0, left)这一段已经全是 0left指向 0 区的下一个空位right(right, n-1]这一段已经全是 2right指向 2 区的上一个空位i当前正在考察的位置它前面的[left, i)全是 1循环条件i right[i, right]才是还没处理的区间i越过right就说明处理完了时间复杂度 O(n)空间 O(1)2. 思路详解第一步两个指针 一个遍历下标各自管什么把整个数组看成四段[ 0 区 ) [ 1 区 ) [ 待处理区 ] ( 2 区 ] 0 left i right n-1[0, left)已排好的 0全是 0[left, i)已排好的 1[i, right]还没看过的部分(right, n-1]已排好的 2。每处理完一个元素就把它塞进对应的段里待处理区随之缩小。等i right待处理区空了整段数组就排好了。第二步三种情况分别怎么处理情况一nums[i] 0。它该去最前面。把它和nums[left]交换——left那个位置正是 0 区的下一个空位换过去正好落位。然后left0 区往前扩一格、i这一位已经处理完了往后看下一个。情况二nums[i] 2。它该去最后面。把它和nums[right]交换——right是 2 区的上一个空位换过去落位。然后right--2 区往前扩一格。情况三nums[i] 1。1 不用挪让它待在原地即可直接i往后看。等 0 和 2 各自归位这些留在中间的 1 自然就聚成了中间的 1 区。第三步为什么 0 要i2 却不i这是这个方法唯一值得琢磨的地方关键看换过来的那个数是谁。遇到 0 时和nums[left]交换。而left永远落在i的左边left ≤ i它左边那段[0, left)全是 0、[left, i)全是 1——所以nums[left]位置上待着的一定是一个 1当left i时而这个 1 早就被考察过了它属于已排好的 1 区。换过来之后nums[i]变成了 1这个 1 本来就该待在中间不用再管所以i可以直接往后走。遇到 2 时和nums[right]交换。而right永远在i的右边它属于还没考察过的待处理区。也就是说nums[right]可能是 2、可能是 1、也可能是 0——换到nums[i]上的这个新值谁也不知道是什么。所以这一位必须留在原地重新考察一遍此时i不能动。一句话概括0 换过来的是已经看过的 1放心往前走2 换过来的是从没见过的数必须停下再看一眼。第四步完整执行过程以示例 1nums [2, 0, 2, 1, 1, 0]为例。初始left 0, right 5, i 0初始: [2, 0, 2, 1, 1, 0] left0 right5 i0 i0: nums[0]2 → 和 nums[5] 换 → [0, 0, 2, 1, 1, 2] right4 i0 换过来的是 0还得再看i 不动 i0: nums[0]0 → 和 nums[0] 换自己换自己 → [0, 0, 2, 1, 1, 2] left1 i1 i1: nums[1]0 → 和 nums[1] 换自己换自己 → [0, 0, 2, 1, 1, 2] left2 i2 i2: nums[2]2 → 和 nums[4] 换 → [0, 0, 1, 1, 2, 2] right3 i2 换过来的是 1是刚看过的类型但要按未考察处理所以留在原地再看 i2: nums[2]1 → 是 1不挪i3 i3: nums[3]1 → 是 1不挪i4 此时 i4 right3待处理区空了循环结束 结果: [0, 0, 1, 1, 2, 2] ✓再看示例 2nums [2, 0, 1]初始: [2, 0, 1] left0 right2 i0 i0: nums[0]2 → 和 nums[2] 换 → [1, 0, 2] right1 i0 i0: nums[0]1 → 是 1i1 i1: nums[1]0 → 和 nums[0] 换 → [0, 1, 2] left1 i2 此时 i2 right1循环结束 结果: [0, 1, 2] ✓可以看到i0那一步换过来的 1 还没被考察过所以停在原地看了一下才发现它是 1才往后走——这正是2 不i的必要性。3. 复杂度分析时间复杂度 O(n)每个元素最多被处理常数次i一路向右、right一路向左合起来推进 O(n) 步。空间复杂度 O(1)只有三个下标变量原地交换。六、总结方法遍历次数时间空间关键点统计个数后重写两遍O(n)O(1)先数再填简单但要多扫一遍双指针三路分区一遍O(n)O(1)0 往左扔、2 往右扔1 留在中间这题的灵魂在于发现只有三个值而且两个极端值各有明确归宿0 该在最左、2 该在最右所以用左右两个指针各守住一端剩下的 1 不用管它会被自然地夹在中间。真正容易写错的是移动下标的时机遇到 0 交换后i因为换回来的一定是已经看过的 1遇到 2 交换后i不动因为从右边换回来的是一个从没考察过的数必须重新判断。把这一点想通了这个双指针就是标准的荷兰国旗问题解法三路分区只扫一遍、只用常数空间。