【分治】--- 快速选择算法

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），而最坏情况下时间复杂度为O(n^2)。同时你也可以这样理解当用基于快速选择的快速排序处理全是重复元素的数组时,一次快速选择就能结束排序了,直接降到O(N)。

思路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问题等，与快排不同的是快速选择只对寻找的的目标所在的子数组进行递归。