题目描述
颜色分类 给定一个包含红色、白色和蓝色，一共 n 个元素的数组，原地对它们进行排序，使得相同颜色的元素相邻，并按照红色、白色、蓝色顺序排列。
此题中，我们使用整数 0、 1 和 2 分别表示红色、白色和蓝色。
注意: 不能使用代码库中的排序函数来解决这道题。
示例:
输入: [2,0,2,1,1,0] 输出: [0,0,1,1,2,2] 进阶：
一个直观的解决方案是使用计数排序的两趟扫描算法。 首先，迭代计算出0、1 和 2 元素的个数，然后按照0、1、2的排序，重写当前数组。 你能想出一个仅使用常数空间的一趟扫描算法吗？
常数空间
快速排序 虽然时间复杂度是O(n)，空间复杂度是O(1) 但递归了两次
class Solution {
public void sortColors(int[] nums
) {
quickSort(nums
,0, nums
.length
-1);
}
public void quickSort(int[] nums
, int left
, int rihght
) {
if (left
> rihght
) {
return;
}
int pivot
=nums
[left
];
int low
= left
;
int high
= rihght
;
while(low
<high
){
while(low
<high
&& nums
[high
]>=pivot
) high
--;
if(low
<high
) nums
[low
++]=nums
[high
];
while(low
<high
&& nums
[low
] < pivot
) low
++;
if(low
<high
) nums
[high
--]=nums
[low
];
}
nums
[low
] = pivot
;
quickSort(nums
,left
,low
-1);
quickSort(nums
,low
+1,rihght
);
}
}
单指针 也算是扫描了两次
class Solution {
public void sortColors(int[] nums
) {
int n
= nums
.length
;
int ptr
= 0;
for (int i
= 0; i
< n
; ++i
) {
if (nums
[i
] == 0) {
int temp
= nums
[i
];
nums
[i
] = nums
[ptr
];
nums
[ptr
] = temp
;
++ptr
;
}
}
for (int i
= ptr
; i
< n
; ++i
) {
if (nums
[i
] == 1) {
int temp
= nums
[i
];
nums
[i
] = nums
[ptr
];
nums
[ptr
] = temp
;
++ptr
;
}
}
}
}
常数空间的一趟扫描算法
双指针1
class Solution {
public void sortColors(int[] nums
) {
int n
= nums
.length
;
int p0
= 0, p1
= 0;
for (int i
= 0; i
< n
; ++i
) {
if (nums
[i
] == 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
;
if (p0
< p1
) {
temp
= nums
[i
];
nums
[i
] = nums
[p1
];
nums
[p1
] = temp
;
}
++p0
;
++p1
;
}
}
}
}
双指针2
class Solution {
public void sortColors(int[] nums
) {
int n
= nums
.length
;
int p0
= 0, p2
= n
- 1;
for (int i
= 0; i
<= p2
; ++i
) {
while (i
<= p2
&& nums
[i
] == 2) {
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
;
}
}
}
}
