文章目录
75.颜色分类1.题目描述2.题目示例3.思路及代码4.题目进阶
75.颜色分类
1.题目描述
给定一个包含红色、白色和蓝色，一共 n 个元素的数组，原地对它们进行排序，使得相同颜色的元素相邻，并按照红色、白色、蓝色顺序排列。
此题中，我们使用整数 0、 1 和 2 分别表示红色、白色和蓝色。
注意: 不能使用代码库中的排序函数来解决这道题。 一个直观的解决方案是使用计数排序的两趟扫描算法。 首先，迭代计算出0、1 和 2 元素的个数，然后按照0、1、2的排序，重写当前数组。
2.题目示例
输入: [2,0,2,1,1,0]
输出: [0,0,1,1,2,2]
3.思路及代码
思路一：利用快速排序思想，将其排序即可，时间复杂度较高，这里不给出代码思路二：题目给出的思路：一个直观的解决方案是使用计数排序的两趟扫描算法。 首先，迭代计算出0、1 和 2 元素的个数，然后按照0、1、2的排序，重写当前数组。代码：
class Solution {
public void sortColors(int[] nums
) {
int zero
= 0;
int one
= 0;
int two
= 0;
for(int i
: nums
){
if(i
== 0){
zero
++;
}else if(i
== 1){
one
++;
}else{
two
++;
}
}
for(int i
= 0; i
< nums
.length
; i
++){
if(i
< zero
){
nums
[i
] = 0;
}else if(i
>= zero
&& i
< zero
+ one
){
nums
[i
] = 1;
}else{
nums
[i
] = 2;
}
}
}
}
4.题目进阶
你能想出一个仅使用常数空间的一趟扫描算法吗？
思路：双指针法
class Solution {
public void sortColors(int[] nums
) {
int left
= 0;
int right
= nums
.length
- 1;
int index
= 0;
while(index
<= right
){
if(nums
[index
] == 0){
swap(nums
, index
, left
);
index
++;
left
++;
}else if(nums
[index
] == 1){
index
++;
}else{
swap(nums
, index
, right
);
right
--;
}
}
}
public void swap(int[] nums
, int l
, int r
){
int temp
= nums
[l
];
nums
[l
] = nums
[r
];
nums
[r
] = temp
;
}
}
