您现在的位置是:首页 >其他 >[Leetcode刷题] - LC075 Sort Colors网站首页其他
[Leetcode刷题] - LC075 Sort Colors
简介[Leetcode刷题] - LC075 Sort Colors
题目描述
一个随机序列包含0,1,2 在不占用额外内存的情况下将序列排序。
题目思路
1. 计数排序
计数排序思路比较简单,记录三个数字出现频率,然后根据频率将0,1,2重新加入数组,思路较为简单。
class Solution {
public void sortColors(int[] nums) {
// count sort
int red = 0;
int white = 0;
int blue = 0;
for (int i: nums) {
if (i==0) red++;
else if (i==2) blue++;
else white++;
}
for (int i=0; i<nums.length; i++) {
if (red!=0) {
nums[i]=0;
red--;
} else if (white!=0) {
nums[i]=1;
white--;
} else {
nums[i]=2;
blue--;
}
}
}
}
时间复杂度:, 需要遍历两遍;空间复杂度:。
2. 对向双指针 + 遍历指针
思路类似快速排序的partition算法,主要需要明确指针遍历时循环不变量,本题循环不变量可以定义为如下:(参考力扣)
循环不变量
定义p0 = 数字0的右边界,p1 = 数字1的右边界,p2 = 数字2的左边界
1. [0, p0) - 左闭右开区间内所有数字 == 0
2. [p0, p1) - 左闭右开区间所有数字 == 1
3. (p2, end] - 左开右闭区间内所有数字 == 2
根据上述循环不变量条件,定义一个三个指针p0, p1, p2 来记录0,1,2的边界,我们可以验证一下这个循环不变量的正确性。
1. 初始时,p0=0, p1=0, p2=nums.length-1, 三个区间内没有值
2. 移动 p1 指针,如果[p0, p1]区间内发现 2,将p1 和 p2的值交换,这样[p2, end]依然满足都是2,可以将p2向左移动一步,但是[p0, p1]经过交换后并不确定是否是1,所以不能移动p1,要在下一次循环中检验
3. 同理,移动 p1 指针,如果[p0, p1]区间内发现 0,将p1 和 p0的值交换,这样[0, p0]依然满足都是0,可以将p0向右移动一步
4. 如果 p1 指针当前值是 1,那么证明[p0, p1]这部分依然满足都是1,p1向右移动一步
代码如下:
class Solution {
public void sortColors(int[] nums) {
int p0 = 0;
int p2 = nums.length-1;
int p1=0;
while(p1<nums.length) {
if (p1<p2 && nums[p1]==2) {
// if [p0, i] has 2 inside then move 2 to [p2, end]
// since after swap, nums[p2] is 2, move p2 to p2-1 then check
// since new nums[i] unknown need to check in next loop
swap(nums, p1, p2);
p2--;
} else if (p1>=p0 && nums[p1]==0) {
// if [p0, i] has 0 inside then move 0 to [0, p0]
// after then nums[p0] is 0, move p0 to p0+1 then check
// since new nums[i] unknown need to check in next loop
swap(nums, p1, p0);
p0++;
} else {
// if [p0, i] is 1, match move to next one
p1++;
}
}
}
private void swap(int[] nums, int a, int b) {
int temp = nums[a];
nums[a] = nums[b];
nums[b] = temp;
}
}
时间复杂度:;空间复杂度:。
风语者!平时喜欢研究各种技术,目前在从事后端开发工作,热爱生活、热爱工作。