LeetCode HOT 100 —— 75 .颜色分类

题目

给定一个包含红色、白色和蓝色、共 n 个元素的数组 nums ，原地对它们进行排序，使得相同颜色的元素相邻，并按照红色、白色、蓝色顺序排列。

我们使用整数 0、 1 和 2 分别表示红色、白色和蓝色。

必须在不使用库内置的 sort 函数的情况下解决这个问题。

思路

本题是经典的荷兰国旗问题，题目的本质是将数分成三段[0...0][1...1][2...2]

除了使用一个变量idx表示处理到哪一个nums[i]之外（即[0,idx-1]的元素均为处理过的元素），还需要两个变量来代表三段的边界

• 变量l为下一个填入0的位置（即[0，l-1]均为0，初始化l=0，表示为空）
• 变量r为下一个填入2的位置（即范围[r+1,n-1]均为2，初始化r=n-1，表示为空）

对于[0,idx−1]的元素中，由于l-1是 0 的右边界，因此[l,idx−1]为1的区间，而[idx,r]为仍未处理的数值

区间分段之后如下图所示：

然后根据当前处理到的nums[idx]进行分情况讨论：

• nums[idx] = 0：将其与位置l进行互换（因为l是下一个待填入0的位置，idx是当前处理到的元素，即[l,idx-1]为1的区间，在上图中相当于是把遍历到的0加入到了前面0区间的末尾 ），这里不需要保持idx继续判断，因为明确知道替换后的nums[idx]为1（因为nums[l] = 1），只需要右移即可
• nums[idx] = 1：由于 [l,idx−1]本身就是 1 的区间，直接将 idx 进行右移即可，在上图中相当于把遍历到的1接到前面的1区间
• nums[idx] = 2：此时将其与位置 r 进行互换（r 为下一个待填入 2 的位置，但 [idx,r]为未处理区间），也就是互换后，只能明确换到位置 nums[r]的位置为 2，可以对 r 进行左移，在上图中相当于把遍历到的2加入到后面2区间的开头，但不确定替换后的新 nums[idx]为何值（这里新nums[idx]相当于就是原来替换前的nums[r]），因此保持 idx 不变接着循环判断。（注意和nums[idx] = 0替换时的区别，替换nums[idx] = 0后的nums[idx]相当于就是nums[l]=1,但是替换nums[idx] = 0后的nums[idx]相当于nums[r]是未知数，不明白的去看我前面画的那个区间图就清晰了）
  最后当idx > r ，即为处理区间为空集，待处理元素全部处理完毕了，整个分三段过程结束

java代码如下：

class Solution{
	public void sortColors(int[] nums){
		int n = nums.length;
		int l = 0, r = n - 1, idx = 0;
		while (idx <= r){
			if (nums[idx] == 0) swap(nums, l++, idx++);//这里idx可以直接++不需要保持再判断，因为nums[l]是确定=1无需再判断
			else if (nums[idx] == 1) idx++;
			else swap(nums, idx, r--);//保持idx不变，继续判断交换后的nums[idx],因为nums[r]是未知的
		}
	}
	
	void swap(int[] nums, int i, int j){
		int temp = nums[i];
		nums[i] = nums[j];
		nums[j] = temp;
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17