天津工程建设信息网站,网络管理协议,服饰品牌网站建设,app推广平台有哪些文章目录 #x1f33f;0. 分治#x1f33b;1. 题目#x1f33c;2. 算法原理#x1f334;3. 代码实现 #x1f33f;0. 分治
分治分治#xff0c;顾名思义分而治之#xff0c;将一个大问题转换成若干个子问题#xff0c;再将这些子问题的基础上继续划分成更小的子问题0. 分治1. 题目2. 算法原理3. 代码实现 0. 分治
分治分治顾名思义分而治之将一个大问题转换成若干个子问题再将这些子问题的基础上继续划分成更小的子问题知道这个子问题能够被快速的解决。 例如学排序的时候快速排序和归并排序都是采用的分治的思想。 对排序内容不清楚的可以查看此篇文章——数据结构——七大排序 1. 题目 题目链接75. 颜色分类 - 力扣LeetCode 给定一个包含红色、白色和蓝色、共 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]提示
n nums.length1 n 300nums[i] 为 0、1 或 2
进阶
你能想出一个仅使用常数空间的一趟扫描算法吗
2. 算法原理
这题有点类似283. 移动零这题只不过这里是要有三个区间可理解为快速排序的三路划分的子问题。
三路肯定要有三个指针left、right、i
left表示0这个区域的最右侧right表示2这个区域的最左侧i来遍历数组
在标记的过程数组会分为四个部分
[0 , left]全都是0[left1 , i-1]全都是1[i , right-1]全都是待扫码的元素[right , n-1]全都是2 这里nums[i]在分情况讨论 nums[i] 0此时要将这个元素加入到左边的区域也就是left1所以要进行一个交换操作swap(nums[left] , nums[i]) 因为这里[left1 , i-1]这个区间的元素都是1所以交换完毕之后直接让i即可 nums[i] 1这里直接让i即可 nums[i] 2此时要将元素加入到right-1这个位置但是不能直接再让i因为right-1这里的元素还未扫码到所以不能i即swap(nums[--right] , nums[i])
3. 代码实现
class Solution {
public:void sortColors(vectorint nums){int left -1, right nums.size(), i 0;while(i right){if(nums[i] 0) swap(nums[left] , nums[i]);else if(nums[i] 1) i;else swap(nums[--right],nums[i]);}}
};运行结果
