AlgoPressAppearance
0075-颜色分类
https://leetcode.cn/problems/sort-colors
给定一个包含红色、白色和蓝色，一共n 个元素的数组，原地对它们进行排序，使得相同颜色的元素相邻，并按照红色、白色、蓝色顺序排列。
此题中，我们使用整数 0、1 和 2 分别表示红色、白色和蓝色。
示例 1：
输入：nums = [2,0,2,1,1,0]
输出：[0,0,1,1,2,2]
示例 2：
输入：nums = [2,0,1]
输出：[0,1,2]
示例 3：
输入：nums = [0]
输出：[0]
示例 4：
输入：nums = [1]
输出：[1]
提示：
n == nums.length
1 <= n <= 300
nums[i] 为 0、1 或 2
进阶：
- 你可以不使用代码库中的排序函数来解决这道题吗？
- 你能想出一个仅使用常数空间的一趟扫描算法吗？
直接思路
代码库的排序方法很简单 Array.Sort(nums);
一趟扫描法: 因为只有 0,1,2 三种数组，所以定义3个指针，一趟扫描。 如果发现0，就和从前面数的第一个非0交换，如果发现2，就和后面数第一个非2数字交换，遇到1不变
参考代码
csharp
public class Solution {
public void SortColors(int[] nums) {
int index0=0;
int index2=nums.Length-1;
for(int i=0; i<index2; i++){
//从后往前不停递进
while(nums[i] == 2 && i <= index2){
int temp = nums[i];
nums[i] = nums[index2];
nums[index2] = temp;
index2--;
}
if(nums[i] == 0){
int temp = nums[i];
nums[i] = nums[index0];
nums[index0] = temp;
index0++;
}
}
}
}
思路1：两次排序 【官方】
csharp
public class Solution {
public void SortColors(int[] nums) {
int p = 0;
//遇到0交换
for(int i = 0; i<nums.Length; i++){
if(nums[i] == 0){
int temp = nums[i];
nums[i] = nums[p];
nums[p] = temp;
p++;
}
}
//遇到1交换
for(int i=p; i<nums.Length; i++){
if(nums[i] == 1){
int temp = nums[i];
nums[i] = nums[p];
nums[p] = temp;
p++;
}
}
}
}
思路2：双指针【官方】
使用两个指针 p0, p1 表示 0 和 1的位置
csharp
public class Solution {
public void SortColors(int[] nums) {
int p0 = 0;
int p1 = 0;
for(int i=0; i<nums.Length; i++){
if(nums[i] == 1){ //交换1
int temp = nums[i];
nums[i] = nums[p1];
nums[p1] = temp;
p1++;
}
else if(nums[i] == 0){
int temp = nums[i];
nums[i] = nums[p0];
nums[p0] = temp;
//交换0的时候，如果前面这个位置已经交换过1，那么必然会把1交换出去，所以需要把1交换回来
if(p0 < p1){
temp = nums[i];
nums[i] = nums[p1];
nums[p1] = temp;
}
p0++;
p1++;
}
}
}
}
思路3：双指针2【官方】
定义 p0, p2 表示 0的指针和2的指针
csharp
public class Solution {
public void SortColors(int[] nums) {
int p0 = 0;
int p2 = nums.Length - 1;
for(int i=0; i<=p2; i++){
//遇到2直接不停地替换到后面
while(nums[i] == 2 && i < p2){
int temp = nums[i];
nums[i] = nums[p2];
nums[p2] = temp;
p2--;
}
if(nums[i] == 0){
int temp = nums[i];
nums[i] = nums[p0];
nums[p0] = temp;
p0++;
}
}
}
}
复习:20220520
csharp
public class Solution {
public void SortColors(int[] nums) {
int p0 = 0; //表示0的结束位置
int p2 = nums.Length-1; //表示2的开始位置
int i=0;
while(i <= p2){
if(nums[i] == 0){
swap(nums,i,p0);
p0++;
i++;
}
else if(nums[i] == 2){
swap(nums,i,p2);
p2--;
}
else{
i++;
}
}
}
private void swap(int[] nums, int i, int j){
int temp = nums[i];
nums[i] = nums[j];
nums[j] = temp;
}
}
复习：20220615
csharp
public class Solution {
public void SortColors(int[] nums) {
int n = nums.Length;
int p0 = 0;
int p2 = n-1;
for(int i=0; i<=p2; i++){
if(nums[i] == 0){ //交换到前面
swap(nums,p0,i);
p0++;
}
else if(nums[i] == 2){ //交换到后面
swap(nums,p2,i);
p2--;
i--; //注意交换到后面之后，当前的数子还需要再处理一下
}
}
}
private void swap(int[] nums, int i, int j){
int tmp = nums[i];
nums[i] = nums[j];
nums[j] = tmp;
}
}