颜色分类
给定一个包含红色、白色和蓝色、共 n 个元素的数组 nums ，原地对它们进行排序，使得相同颜色的元素相邻，并按照红色、白色、蓝色顺序排列。
我们使用整数 0、 1 和 2 分别表示红色、白色和蓝色。
必须在不使用库的sort函数的情况下解决这个问题。
示例 1：
1
2
| 输入：nums = [2,0,2,1,1,0]
输出：[0,0,1,1,2,2]
|
示例 2：
1
2
| 输入：nums = [2,0,1]
输出：[0,1,2]
|
解法一：快速排序
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
30
31
| class Solution {
public void sortColors(int[] nums) {
quick(nums,0,nums.length-1);
}
public void quick(int []nums,int l,int r){
if (l<r){
int index = sort(nums,l,r);
quick(nums,l,index-1);
quick(nums,index+1,r);
}
}
public int sort(int []nums,int l,int r){
int t = nums[l];
while (l<r){
while (l<r && nums[r]>=t){
r--;
}
if (nums[r]<t){
nums[l] = nums[r];
}
while (l<r &&nums[l]<=t){
l++;
}
if (nums[l]>t){
nums[r] = nums[l];
}
}
nums[l] = t;
return l;
}
}
|
解法二：单指针
- 两次遍历数组，定义指针，开始指向0
- 第一次遍历数组，寻找数组中数字是0的与指针交换，指针后移
- 第二次遍历数组，寻找数组中数字是1的与指针交换，指针后移
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
| class Solution {
public void sortColors(int[] nums) {
int p0 = 0;
int n = nums.length;
for (int i = 0;i<n;i++){
if (nums[i]==0){
int t = nums[i];
nums[i] = nums[p0];
nums[p0] = t;
p0++;
}
}
for (int i = p0;i<n;i++){
if (nums[i]==1){
int t = nums[i];
nums[i] = nums[p0];
nums[p0] = t;
p0++;
}
}
}
}
|
解法三：双指针
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
| class Solution {
public void sortColors(int[] nums) {
int p0 = 0;
int p1 = 0;
int n = nums.length;
for (int i = 0;i<n;i++){
if (nums[i]==1){
int t = nums[i];
nums[i] = nums[p1];
nums[p1] = t;
p1++;
}else if (nums[i]==0){
int t = nums[i];
nums[i] = nums[p0];
nums[p0] = t;
if (p0<p1){
t = nums[i];
nums[i] = nums[p1];
nums[p1] = t;
}
p0++;
p1++;
}
}
}
}
|
解法四：计数
分别算出0，1，2的个数，再依次填入
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
| class Solution {
public void sortColors(int[] nums) {
int n0 = 0;
int n1 = 0;
int n2 = 0;
for (int i = 0;i<nums.length;i++){
if (nums[i]==0){
n0++;
}else if (nums[i]==1){
n1++;
}else {
n2++;
}
}
for (int i = 0;i<nums.length;i++){
if (i<n0){
nums[i] = 0;
}else if (i<n0+n1){
nums[i] = 1;
}else {
nums[i] = 2;
}
}
}
}
|