题目描述
给定一个包含红色、白色和蓝色、共 n 个元素的数组 nums ，原地对它们进行排序，使得相同颜色的元素相邻，并按照红色、白色、蓝色顺序排列。
我们使用整数 0、 1 和 2 分别表示红色、白色和蓝色。
必须在不使用库的sort函数的情况下解决这个问题。
示例 1：
输入：nums = [2,0,2,1,1,0]
输出：[0,0,1,1,2,2]
示例 2：
输入：nums = [2,0,1]
输出：[0,1,2]
题解
思路1:双指针
指针left 初始位置为0，表示红色下一个填充位置，left指针递增，指针right初始为n-1，表示蓝色下一个填充位置，right指针递减
遍历数组nums，下标为check，如果check>right,即遍历结束，如果nums[check] == 0,则交换left和check的位置，left++，check++，如果nums[check] == 2,则交换right和check的位置，right--，此处check不+1，因为交换后的check位置可能是0，加1会漏掉这个0,如果nums[check] !=0 && nums[check] !=2,则check++
// OC
+ (void)sortColors1:(NSMutableArray *)nums {
int n = (int)nums.count;
int check = 0;
int left = 0;
int right = n - 1;
while (check <= right) {
if ([nums[check] intValue] == 0) {
[self swap1:nums i:check j:left];
left ++;
}
if ([nums[check] intValue] == 2) {
[self swap1:nums i:check j:right];
right --;
// 交换后 nums[check] 可能为0，防漏
check --;
}
check ++;
}
}
+ (void)swap1:(NSMutableArray *)nums i:(int)i j:(int)j {
id temp = nums[i];
nums[i] = nums[j];
nums[j] = temp;
}
// Swift
static public func sortColors1(_ nums: inout [Int]) {
let n = nums.count
var left = 0
var right = n-1
var check:Int = 0
while check<=right {
if nums[check] == 0 {
swap1(&nums, check, left)
left += 1
}else if nums[check] == 2 {
swap1(&nums, check, right)
right -= 1
check -= 1
}
check += 1
}
}
static func swap1(_ nums: inout [Int], _ i:Int, _ j:Int) {
let temp = nums[i]
nums[i] = nums[j]
nums[j] = temp
}
思路2:单指针
在第一次遍历中，我们将数组中所有的0 交换到数组的头部。在第二次遍历中，我们将数组中所有的1 交换到头部的0 之后。此时，所有的2 都出现在数组的尾部，这样我们就完成了排序。
指针left初始位置为0，表示红色(0)下一个填充位置，left指针递增，遍历数组nums，将所有红色都交换到数组的左边。
第一次遍历完数组后，假设指针left值为a，那么a的左边都是红色，再次遍历数组nums，指针left表示白色(1)下一个填充位置，初始为a，将所有白色都交换到数组的左边
// OC
+ (void)sortColors2:(NSMutableArray *)nums {
int n = (int)nums.count;
int left = 0;
for (int i=0; i<n; i++) {
if ([nums[i] intValue] == 0) {
[self swap2:nums i:i j:left];
left ++;
}
}
for (int i=left; i<n; i++) {
if ([nums[i] intValue] == 1) {
[self swap2:nums i:i j:left];
left ++;
}
}
}
+ (void)swap2:(NSMutableArray *)nums i:(int)i j:(int)j {
id temp = nums[i];
nums[i] = nums[j];
nums[j] = temp;
}
// Swift
static public func sortColors2(_ nums: inout [Int]) {
let n = nums.count
var left = 0
for i in 0..<n {
if nums[i] == 0 {
swap2(&nums, i, left)
left += 1
}
}
for i in left..<n {
if nums[i] == 1 {
swap2(&nums, i, left)
left += 1
}
}
}
static func swap2(_ nums: inout [Int], _ i:Int, _ j:Int) {
let temp = nums[i]
nums[i] = nums[j]
nums[j] = temp
}
思路3:双指针
指针p0用于交换0，p1用于交换1,初始都为0。从左到右遍历数组nums
- 找到1时，就将nums[p1]和nums[i]交换，p1+1，继续下一次遍历
- 找到0时，将nums[p0]和nums[i]交换，p0+1，继续下一次遍历，但如果这样做，会存在问题，在p0<p1时。直接将nums[p0]和nums[i]交换，会把一个1交换到i位置。因此在p0<p1时，我们需要再将nums[i]和nums[p1]交换，将1再交换到头部位置。无论p0是否小于p1,我们都需要将p0+1，p1+1
// OC
+ (void)sortColors3:(NSMutableArray *)nums {
int n = (int)nums.count;
int p0 = 0;
int p1 = 0;
for (int i=0; i<n; i++) {
if ([nums[i] intValue] == 1) {
[self swap3:nums i:i j:p1];
p1 ++;
}
if ([nums[i] intValue] == 0) {
[self swap3:nums i:i j:p0];
// 在p0<p1时。直接将nums[p0]和nums[i]交换，会把一个1交换到i位置。因此在p0<p1时，我们需要再将nums[i]和nums[p1]交换，将1再交换到头部位置
if (p0 < p1) {
[self swap3:nums i:i j:p1];
}
p0 ++;
p1 ++;
}
}
}
+ (void)swap3:(NSMutableArray *)nums i:(int)i j:(int)j {
id temp = nums[i];
nums[i] = nums[j];
nums[j] = temp;
}
// Swift
static public func sortColors3(_ nums: inout [Int]) {
let n = nums.count
var p0 = 0
var p1 = 0
for i in 0..<n {
if nums[i] == 1 {
swap3(&nums, i, p1)
p1 += 1
}
if nums[i] == 0 {
swap3(&nums, i, p0)
// 此时会将1交换出去
if p0 < p1 {
// 再次交换p1和i
swap3(&nums, i, p1)
}
p0 += 1
p1 += 1
}
}
}
static func swap3(_ nums: inout [Int], _ i:Int, _ j:Int) {
let temp = nums[i]
nums[i] = nums[j]
nums[j] = temp
}
思路4:双指针
指针p0用于交换0,初始为0，p2用于交换2,初始为n-1。从左到右遍历数组nums
- 找到2时，将nums[p2]和nums[i],p2-1,继续下一次遍历，但这样可能存在问题，nums[p2] 和 nums[i] 交换后，新的nums[i]可能还是2，如果直接继续下一次遍历的后，那i位置的2就没有交换到最右边。因而，我们需要不断的交换num[i]和p2,直到num[i]不为2
- 找到0时，将nums[p0]和nums[i]交换，p0+1，继续下一次遍历
// OC
+ (void)sortColors4:(NSMutableArray *)nums {
int n = (int)nums.count;
int p0 = 0;
int p2 = n-1;
int check = 0;
while (check <= p2) {
// 不断的交换num[i]和p2,直到num[i]不为2
while (check<=p2 && [nums[check] intValue] == 2) {
[self swap4:nums i:check j:p2];
p2 --;
}
if ([nums[check] intValue] == 0) {
[self swap4:nums i:check j:p0];
p0 ++;
}
check ++;
}
}
+ (void)swap4:(NSMutableArray *)nums i:(int)i j:(int)j {
id temp = nums[i];
nums[i] = nums[j];
nums[j] = temp;
}
// Swift
static public func sortColors4(_ nums: inout [Int]) {
let n = nums.count
var p0 = 0
var p2 = n-1
var check = 0
while check <= p2 {
// 不断的交换num[i]和p2,直到num[i]不为2
while check<=p2 && nums[check] == 2 {
swap4(&nums, check, p2)
p2 -= 1
}
if nums[check] == 0 {
swap4(&nums, check, p0)
p0 += 1
}
check += 1
}
}
static func swap4(_ nums: inout [Int], _ i:Int, _ j:Int) {
let temp = nums[i]
nums[i] = nums[j]
nums[j] = temp
}
参考：https://leetcode-cn.com/leetbook/read/top-interview-questions-medium/xvg25c/
https://leetcode-cn.com/problems/sort-colors/solution/yan-se-fen-lei-by-leetcode-solution/
