大家好，又见面了，我是你们的朋友全栈君。如果您正在找激活码,请点击查看最新教程,关注关注公众号 “全栈程序员社区” 获取激活教程,可能之前旧版本教程已经失效.最新Idea2022.1教程亲测有效,一键激活。
Jetbrains全系列IDE使用 1年只要46元 售后保障 童叟无欺
给定一个包含红色、白色和蓝色，一共 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
进阶：
你可以不使用代码库中的排序函数来解决这道题吗？
你能想出一个仅使用常数空间的一趟扫描算法吗？
题解
- 快排
class Solution {
public:
void quick(int l,int r,vector<int>& nums){
if(l < r){
int mid = partion(l,r,nums);
quick(l,mid - 1,nums);
quick(mid + 1,r,nums);
}
}
int partion(int l,int r,vector<int>&nums){
int key = nums[l];
while(l < r){
while(l < r && nums[r] > key)r --;
if(l < r)nums[l ++] = nums[r];
while(l < r && nums[l] < key)l ++;
if(l < r)nums[r --] = nums[l];
}
nums[l] = key;
return l;
}
void sortColors(vector<int>& nums) {
int l = 0,r = nums.size() - 1;
quick(l,r,nums);
}
};
- 因为只有3组数字，最左边有一组，最右边有一组，中间有一组，所以把最左边和最右边都规整后，中间自然就规整，所以设置i,j代表左边放置0的下边，j为右边放置2的下标.
时间复杂度O(n)
class Solution {
public:
void sortColors(vector<int>& nums) {
int i = 0,n = nums.size(),j = nums.size() - 1;
while(i < n && nums[i] == 0)i ++;
while(j >= 0 && nums[j] == 2)j --;
for(int k = i;k <= j;k ++){
if(nums[k] == 0)swap(nums[i],nums[k]),i ++;
else if(nums[k] == 2)swap(nums[j],nums[k]),k --,j --; //注意当从后面换回去的时候可能回把后面的0换到前面
}
}
};
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 举报，一经查实，本站将立刻删除。
发布者：全栈程序员-站长，转载请注明出处：https://javaforall.net/169157.html原文链接：https://javaforall.net
