大家好,又见面了,我是你们的朋友全栈君。如果您正在找激活码,请点击查看最新教程,关注关注公众号 “全栈程序员社区” 获取激活教程,可能之前旧版本教程已经失效.最新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换到前面
}
}
};
发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/169157.html原文链接:https://javaforall.cn
【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛
【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...