力扣-75-颜色分类

题目:
75. Sort Colors(medium)


题目大意:
给定一个包含红色、白色和蓝色,一共 n 个元素的数组,原地对它们进行排序,使得相同颜色的元素相邻,并按照红色、白色、蓝色顺序排列。
此题中,我们使用整数 0、 1 和 2 分别表示红色、白色和蓝色。
注意:
不能使用代码库中的排序函数来解决这道题。

1
2
3
示例:
输入: [2,0,2,1,1,0]
输出: [0,0,1,1,2,2]

进阶:
一个直观的解决方案是使用计数排序的两趟扫描算法。
首先,迭代计算出0、1 和 2 元素的个数,然后按照0、1、2的排序,重写当前数组。
你能想出一个仅使用常数空间的一趟扫描算法吗?


解题思路:
要求:原地排序,只进行一边扫描,
简化成对0,1,2进行排序。
看了官方题解,才知道这个问题是一种典型问题——“荷兰国旗问题”。利用三个指针分别来追踪0的最右界p0、当前遍历位置cur和2的最左边界p2。整体思路是数组遍历cur指针,若nums[cur]=0,将其与nums[p0]互换,p0++;若nums[cur]=2,将其与nums[p2]互换,p2—。

题解中还有一种解法解法,本质上和上面那个解法相同,但是这里说算法是基于三路快排的思想,而且思考过程和编程习惯也写的非常用心。


代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
Java:

public void sortColors(int[] nums){
//p0:0的最右边界 cur:当前元素 p2:2的最左边界
int p0 = 0,cur = 0,p2 = nums.length - 1;
while(cur <= p2){//此处等号是为了cur能把2之前的位置遍历完
if(nums[cur] == 0){
swap(nums,p0++,cur);
cur++;
//当前元素等于0时,cur和p0都要++
//因为可以确定之前的部分全是0

}else if(nums[cur] == 2){
swap(nums,cur,p2--);
//当前元素等于2时,只有p2--
//因为不能确定目前换到cur位置的数是0还是1
//需要继续判断
}else{
cur++;
//当前元素等于1时,cur只需++就行
}
}
}

private void swap(int[] nums,int i,int j){
int temp = nums[i];
nums[i] = nums[j];
nums[j] = temp;
}