海南省建设注册中心网站,网站的超链接怎么做,婚车租赁,网站代码优化有哪些目录 颜色分类#xff08;数组分三块思想#xff09;快速排序归并排序 颜色分类#xff08;数组分三块思想#xff09; 给定⼀个包含红⾊、⽩⾊和蓝⾊、共 n 个元素的数组 nums #xff0c;原地对它们进⾏排序#xff0c;使得相同颜⾊ 的元素相邻#xff0c;并按照红⾊、… 目录 颜色分类数组分三块思想快速排序归并排序 颜色分类数组分三块思想 给定⼀个包含红⾊、⽩⾊和蓝⾊、共 n 个元素的数组 nums 原地对它们进⾏排序使得相同颜⾊ 的元素相邻并按照红⾊、⽩⾊、蓝⾊顺序排列。 我们使⽤整数 0、 1 和 2 分别表⽰红⾊、⽩⾊和蓝⾊。 必须在不使⽤库的 sort 函数的情况下解决这个问题。 示例 1 输⼊nums [2,0,2,1,1,0] 输出[0,0,1,1,2,2] class Solution {
public:void sortColors(vectorint nums) {int i 0;int left i-1;int right nums.size();//数组分三块while(iright){if(nums[i] 1) i;else if(nums[i] 0) {swap(nums[i],nums[left]);i;}else swap(nums[i],nums[--right]);}}
};快速排序
类似于前序遍历先分块再分治。
class Solution {
public:vectorint sortArray(vectorint nums) {qsort(nums,0,nums.size()-1);return nums;}void qsort(vectorint nums,int l,int r){//递归结束条件if(l r) return;//要么区间不存在要么只剩下一个元素int i l;int left l-1,right r1;int key nums[i];//数组分块while(i right){if(nums[i]key) i;else if(nums[i] key) {swap(nums[i],nums[left]);i;}else swap(nums[i],nums[--right]);}//分治qsort(nums,l,left);qsort(nums,right,r);}
};归并排序
类似于后序遍历先分治再归并。
class Solution {
public:vectorint temp;vectorint sortArray(vectorint nums) {temp.resize(nums.size());msort(nums,0,nums.size()-1);return nums;}void msort(vectorint nums,int left,int right){//递归结束条件if(leftright) return;//先分治int mid (left right) 1;msort(nums,left,mid);msort(nums,mid1,right);//归并int cur1 left;//遍历左区间int cur2 mid1;//遍历右区间int i 0;//temp数组使用while(cur1 mid cur2 right){if(nums[cur1]nums[cur2]) temp[i] nums[cur2];else temp[i] nums[cur1];}while(cur1 mid) temp[i] nums[cur1];while(cur2 right) temp[i] nums[cur2];for(int i left;i right ;i){nums[i] temp[i-left];//i-left 0}}
};
