【分治】--- 快速选择算法
Welcome to 9ilk's Code World
(๑•́ ₃ •̀๑) 个人主页: 9ilk
(๑•́ ₃ •̀๑) 文章专栏： 算法Journey
🏠 颜色划分
📌 题目解析
颜色分类
- 本题要求我们原地对元数组划分0,1,2三个区域,也就是不能使用辅助数组，同时不能使用库中内置的sort函数。
📌 算法原理
【双指针算法】--- 移动零 && 复写零_移动零 双指针-CSDN博客
在做这道题中，我们可以复习一下移动零的思路。在这道题中也是要求我们对数组进行划分，只不过划分为非0和0两个区域。移动零这道题中可以使用双指针dest和cur来界定非0和0两个区域，当进行遍历数组的指针cur遇到非0的数时，此时需要移动dest将这个非0的数并入[0,dest]区间；当遇到0时，此时0就是在[dest,cur]的区域内，只需让cur继续移动即可；最后直到cur遍历完数组。
类比移动零的思路，我们可以先把数组划分为全是2和非2的区域，然后再把非2的区域划分为非1和1的区域：
class Solution {
public:// 思路:三指针// 首先将整个数组划分为两块void sortColors(vector<int>& nums) {int cur = 0;int dest = -1;// 第一次划分左边是0,1 右边是2while (cur < nums.size()) {if (nums[cur] == 2)cur++;else {dest++;swap(nums[dest], nums[cur]);cur++;}}// 划分左边区域cur = 0;dest = -1;while (cur < nums.size()) {if (nums[cur] == 2)break;if (nums[cur] == 1)cur++;else if(nums[cur] == 0){dest++;swap(nums[dest], nums[cur]);cur++;}}}
};我们能否让cur指针遍历完数组的同时，一次性把三个区域划分好呢？
我们可以规定：[0,left]属于全都是0的区域，[left+1,i-1]属于全是1的区域，[right,n-1]属于全都是2
的区域，而同样的我们需要一个遍历数组的指针i，因此[i,right]属于待扫描的区域。
Q：为什么i遇到2交换完后i不能向前移动,而遇到1时可以?
--right之后,right所处的位置是待扫描的,此时交换过来之后不知道是0/1/2,仍然需要处理,需要重新判断;而++left之后,由于left所处的位置是i扫描过的,所以可以放心交换。
Q：i遍历到何时结束？
当i遍历到right时说明三个区域 已经划分完了，没有继续往后走的必要了。
参考代码：
class Solution {
public:void sortColors(vector<int>& nums){int n = nums.size();int left = -1;int i = 0;int right = n;while (i != right){if (nums[i] == 0) swap(nums[++left], nums[i++]);else if (nums[i] == 1)i++;elseswap(nums[--right], nums[i]);}}
};🏠 排序数组
📌 题目解析
排序数组
- 本题也不允许使用内置函数比如sort()。
📌 算法原理
本题我们采用快速排序求解下。
先回忆一下简单的一个快速排序的基本思想：
- 先确定一个基准key。
- right移动时寻找比key小的，left移动时寻找比key大的。
- swap(nums[right],nums[left]);
- 数组被划分为左边是小于key，右边是大于key。
- 左边部分也按照上述逻辑处理，右边部分也这样处理,直到无法再划分区间。
快速排序整体思想中主要也是对数组进行区域划分，将左边划分为小于等于key,右边划分大于key,但是本道题单纯这样写一个快排是会超时的，当数组都是重复的元素时，此时快排会退化为O(N^2)。如果我们使用前面的"数组分三块"的三路划分思想，此时处理完整个数组，处理左右两边时就不需要处理重复元素了，因为重复元素都被划分进中间区域了！
总结步骤：
优化 : 在常规快排中，我们常选取左端的第一个数作为key，当数组接近有序时，此时会退化为O(N^2),此时我们可以采取三数取中/随机数尽可能避免这种极端情况。同时我们选择随机数时可以选择让rand()%(right-left+1)使取值范围为[left,right]，再加上left之后就能映射到我们选的区间。
参考代码:
class Solution {
public:void QuickSort(vector<int>& nums, int left, int right){if (left >= right)return;int randi = rand()%(right-left+1);randi += left; //随机数int key = nums[randi];int i = left;int begin = left - 1;int end = right + 1 ;while (i != end){ if(nums[i] < key)//< key区域swap(nums[++begin],nums[i++]);else if(nums[i] == key) // ==key区域i++;else // > key区域swap(nums[--end],nums[i]);}//排左边 右边QuickSort(nums, left, begin);QuickSort(nums, end, right);}vector<int> sortArray(vector<int>& nums){srand(time(NULL));QuickSort(nums, 0, nums.size() - 1);return nums;}
};🏠 数组中的第k大个元素
📌 题目解析
数组中的第K个最大元素
- 本题需要设计时间复杂度为O(N)的算法。
📌 算法原理
- 思路1：排序 + 计数器
class Solution {
public:int findKthLargest(vector<int>& nums, int k){ sort(nums.begin(),nums.end());int cur = nums.size() - 1;int count = 0;while(count < k){count++;if(count < k)cur--;}// 1 2 3 4 5 6 k = 2return nums[cur];}
};- 思路2 ：堆排序(Top K)
class Solution {
public:
//建大堆int findKthLargest(vector<int>& nums, int k){ priority_queue<int> pq(nums.begin(),nums.end());while(k>1){pq.pop();k--;}return pq.top();}
};- 思路3 ：桶排序
前面两种思路虽然能解决问题，但严格讲并不是O(N)的时间复杂度，而桶排序就完美的符合，但是需要空间换时间，我们可以根据题目给定的数据范围开好数组进行映射。
class Solution {
public:
//桶排序 相对映射 int findKthLargest(vector<int>& nums, int k){ int arr [20001] = {0};//遍历nfor(auto e : nums){arr[e+10000]++;}int num = 0;//遍历20001for(int i = 20000;i>=0;i--){k = k - arr[i];if(k <= 0){num = i-10000;break;}}return num;}
};- 思路4：快速选择算法
基于快速选择算法,我们可以快速划分出三个区域,基于三个区域各自元素个数定位出第k大元素的区间。
参考代码：
class Solution {
public:int QuickSort(vector<int>& nums,int left,int right,int k){if(left == right)return nums[left];int key = nums[left];int begin = left-1;int end = right+1;int i = left;while(i < end){if(nums[i] < key) swap(nums[++begin],nums[i++]);else if(nums[i] == key) i++;else swap(nums[--end],nums[i]); } // [left,begin] (begin,end) [end,right]int midNum = end - begin - 1;int RightNum = right - end + 1;if (LeftNum >= k) return QuickSort(nums, left, begin, k);else if (midNum + LeftNum >= k) return key;elsereturn QuickSort(nums, end, right, k - midNum - LeftNum);}int findKthLargest(vector<int>& nums, int k){return QuickSort(nums,0,nums.size()-1,k); }
};注：考虑到退化的情况我们可以自行采取随机数/三路取中的优化方法。
快速选择算法也常常用于解决TopK问题,和快排不同的是，快速选择并不对左右两部分子数组都进行递归，而只对寻找的目标所在的子数组进行递归。也正因如此，快速选择算法将平均时间复杂度从O(nlogn)降到O(n），而最坏情况下我们不能保证每次选取的key是中间值，此时时间复杂度会退化为O(n^2)，为了尽可能防止极端情况发生，我们需要在算法开始的时候对
nums数组来一次随机打乱。关于快速选择算法的时间复杂度计算可参考这篇文章：快速选择
- 思路5：库函数
nth_element函数第一个参数是起始位置，第二个参数是要查找元素的位置，第三个参数是最后一个元素位置+1；nth_element(a,a+k,a+n)意思就是把数组中第k小(默认是第k小)的数放在k下标，而对其他元素没有排序，但是k左边都是比它小的，k右边都是比它大的。如果你想求第k大，可以传第四个参数也就是仿函数，也可以将求第k大转化为求第n-k+1小，对应就是array[n-k];
class Solution
{
public:int findKthLargest(vector<int>& a, int k) {int n = a.size();nth_element(a.begin(),a.begin()+n-k,a.end());return a[n-k];}
};🏠 最小的k个数
📌 题目解析
最小的k个数
- 本题要返回的不是第k小的数，而是要返回前k小的所有数，顺序不限。
📌 算法原理
- 思路1：排序(NlogN)
- 思路2：堆(Nlogk)
- 思路3:快速选择算法 O(N)
当快速选择完之后就能把数组划分为三个区域，左边是比第k小还要小的数，中间是第k小，右边是比第k小的数还要大的数，我们直接返回左边和中间即可。
参考代码：
vector<int> getLeastNumbers(vector<int>&nums, int k)
{ srand(time(NULL));qsort(nums,0,nums.size()-1,k);return{nums.begin(),nums.begin()+k
};
void qsort(vector<int>&nums,int l,int 1, int r, int k)
{if(l>=r)return;
//1.随机选择一个基准元素+数组分三块 int key = getRandom(nums,1,r);int left=1,right=right=r +1, i = 1, i = 1;while(i<right){if(nums[i]<key) swap(nums[++left],nums[i++]);else if(nums[i]== key) i++;else swap(nums[--right],nums[i]);}// [1,left][left + 1, right - 1][right,r]//2.分情况讨论int a = left-1+1,b=right-left-1;if(a>k) qsort(nums,1,left,k);else if(a+b>=k)return;else qsort(nums,right,r,k-a - a - b);
}
int getRandom(vector<int>&nums,intl,int l, int r)
{return nums[rand() %(r-1+1)+1)+1) + 1];
}总结: 本篇博客我们介绍了快速排序的衍生算法快速选择算法,本算法也是基于分治的思想进行快速定位区间,其可以使某些需要 O(nlogn)时间复杂度的问题，在平均复杂度O(n)下完成。常见的例子是求数组的第
k小的数，Top k问题等，与快排不同的是快速选择只对寻找的的目标所在的子数组进行递归。同时我们介绍了当数组全是重复元素时对快排的优化方案：三路划分。