算法练习——分治_快排
前言的前言：大佬写博客给别人看，菜鸟写博客给自己看，我是菜鸟
前言：分治_快排的核心思想是将数据分成三部分，对每一部分数据进行讨论和处理，再通过递归的重复上述步骤得到最终结果。
注：
1.在分治_快排算法中，我们需要用到三指针去解决问题。
2.这种先处理再递归的思路，相当于树中 前序遍历 的过程。这点需和 分治_归并 算法做区分
一：颜色分类
题目要求：
解题思路：
思路：以示例1为例，根据分治_快排算法的思路，可以如下图定义三个指针，然后遍历数组。
这里的基准值为 key = 1;
①：当 nums[i] > key 时，swap(nums[i],nums[--right]);
②：当 nums[i] < key 时，swap(nums[i++],nums[++left]);
③：当 nums[i] == key 时，i++；
问：为什么一个需要 i++，一个不需要？
答：若i位置元素为2，大于基准值，需要和 --right 位置处的元素交换，此时从right位置交换来的数据可能是0或1，如果是0的话，那么当前位置元素需要进一步和 ++left 位置处的元素做进一步交换，因此①中不可以执行i++。而对于②而言，首先交换过来的元素不可能是2，因为 left在左，i在右，元素2 肯定在先前遍历中被处理掉了，因此交换后 i 位置的元素只可能是1，而1本该就处于中间位置，因此①可以直接++
上述过程执行完毕后，可以得到如下结果：
实现代码：
void sortColors(vector<int>& nums) {
int left = -1, right = nums.size(), i = 0;
int key = 1;
while(i < right)
{
if(nums[i] > key) {
swap(nums[--right],nums[i]);
}
else if (nums[i] == key) {
i++;
}
else {
swap(nums[i++],nums[++left]);
}
}
}二：排序数组
题目要求：
解题思路：
思路：同为分治_快排的算法题，因此核心思想和上题本质上是没有区别的，但是有几个注意点。
(1)、本题中基准值不固定，因此需要通过随机值给基准值key进行赋值(此方法是优于三数取中的方法，相关证明这里不做叙述)
srand(time(NULL)); int key = nums[rand()%(r-l+1)+l]; //l为当前数组段最左端数据，r为当前数组段最右侧数据 //为什么说是数组段，因为本题还会用到递归的方法，每次递归可不是从0开始(2)、有了基准值后，便可以通过以下思路来进行数组分类
①：当 nums[i] > key 时，swap(nums[i],nums[--right]);
②：当 nums[i] < key 时，swap(nums[i++],nums[++left]);
③：当nums[i] == key 时，i++；
完成上述逻辑后，数组中元素分布如下：
注：l为当前数组段最左端元素，r为当前数组段最右端元素
(3)、此时数组中元素分布并未满足要求，因此我们需要用到递归的思想，排列 l~left，right~r两个区间的元素。
实现代码：
int get_random(vector<int>& nums, int l, int r) {
return nums[rand()%(r-l+1)+l];
}
void q_sort(vector<int>& nums, int l, int r) {
if(l >= r) {
return;
}
int left = l - 1, right = r + 1, i = l;
int key = get_random(nums,l,r);
while(i < right) {
if(nums[i] > key) {
swap(nums[i],nums[--right]);
}
else if (nums[i] == key) {
i++;
}
else {
swap(nums[i++],nums[++left]);
}
}
q_sort(nums,l,left);
q_sort(nums,right,r);
}
vector<int> sortArray(vector<int>& nums) {
srand(time(NULL));
q_sort(nums,0,nums.size()-1);
return nums;
}三：数组中的第K个最大元素
题目要求：
解题思路：
思路：核心想法和上一题是没有区别的，但是需要有几个注意的地方。
(1)、按照上一题的思路
①：当 nums[i] > key 时，swap(nums[i],nums[--right]);
②：当 nums[i] < key 时，swap(nums[i++],nums[++left]);
③：当nums[i] == key 时，i++；
我们会得到如图所示的结果：
注：l为当前数组段最左端元素，r为当前数组段最右端元素
(2)、题目要求我们统计第K个大的元素，因此我们只需关注数组段右端部分，即较大的那部分数据，为此我们需要将K和每个部分元素个数进行比较，从而进行下一步的递归。
①：当 k <= (r - right + 1)，只需递归 right ~ r 区间
②：当 k <= (r - left)，说明此时第K大的元素恰好是基准值，直接返回基准值
③：当 k <= (r - l + 1) (该条件其实为上述两个条件的 else,代码中不写),只需递归l~left 区间，此时 k 需要减去 r - left，
问：为什么 ③ 中 k 要减去 r - left
答：在③中，我们只需递归 l~left 区间，因此大于 left 部分的区间被舍弃，此时相当于前k个大的数据全部被舍弃了，因此k也要跟着减去 r - left 个，这样才能找到对应的数。
注：上述思想可以大大减少递归和排序的次数，从而达到优化算法的目的，例如当满足第一个条件时，就不用考虑前两个区间，只需考虑第三个区间。
实现代码：
int get_random(vector<int>& nums, int l, int r) {
return nums[rand()%(r-l+1)+l];
}
int q_sort(vector<int>& nums, int l, int r, int k) {
if(l >= r) {
return nums[l];
}
int left = l - 1, right = r + 1, i = l;
int key = get_random(nums,l,r);
while(i < right) {
if(nums[i] > key) {
swap(nums[i],nums[--right]);
}
else if (nums[i] == key) {
i++;
}
else {
swap(nums[i++],nums[++left]);
}
}
int a = r - right + 1, b = r - left;
if(a >= k) {
return q_sort(nums,right,r,k);
}
else if (b >= k) {
return key;
}
else {
return q_sort(nums,l,left,k - b);
}
}
int findKthLargest(vector<int>& nums, int k) {
srand(time(NULL));
return q_sort(nums,0,nums.size()-1,k);
}四：库存管理Ⅲ
题目要求：
解题思路：
思路：
(1)、按照下述条件，将数组排列
①：当 nums[i] > key 时，swap(nums[i],nums[--right]);
②：当 nums[i] < key 时，swap(nums[i++],nums[++left]);
③：当nums[i] == key 时，i++；
得到如下图所示的数组
注：l为当前数组段最左端元素，r为当前数组段最右端元素
(2)、题目要求是最小的cnt个，因此需要将cnt与每个部分的元素个数进行比较
①：当cnt <= left - l + 1，区间 l~left 内的元素不一定满足要求，需要递归重新排序
②：当cnt <= right - l + 1, 递归结束，直接返回
③：当cnt <= r - l + 1,说明 right 左边的区域已经全是较小数，而区间 right~r 内元素不一定满足要求，因此需要重新递归排序，同时此时 cnt -= right - l
问：为什么③中需要 -= right - left？
答：区间 l~(right-1)内较小的元素个数少于cnt，需要在 right~r 区间中，再找 cnt - (right-left) 个较小的元素，才能满足最终结果。
实现代码：
int get_random(vector<int>& nums, int l, int r) {
return nums[rand()%(l-r)+l];
}
void q_sort(vector<int>& nums, int l, int r, int k) {
if(l >= r) {
return;
}
int left = l - 1, right = r + 1, i = l;
int key = get_random(nums, l, r);
while( i < right) {
if(nums[i] > key) {
swap(nums[i],nums[--right]);
}
else if (nums[i] == key) {
i++;
}
else {
swap(nums[i++],nums[++left]);
}
}
int a = left - l + 1, b = right - l;
if(k < a) {
q_sort(nums, l, left, k);
}
else if (k < b) {
return;
}
else {
q_sort(nums, right, r, k - b);
}
}
vector<int> inventoryManagement(vector<int>& nums, int k) {
srand(time(NULL));
q_sort(nums, 0, nums.size()-1, k);
return {nums.begin(),nums.begin()+k};
}