分治(2)——快速搜索算法
欢迎来到博主的专栏:算法解析
博主ID:代码小豪
leetcode215——数组中的第k个最大元素
题目解析
此类在数组中,寻找第k大,第k小,前k大,前k小的OJ问题,通常我们会称其为topk问题,通常这类问题的解法有以下几种。
- 1.堆排序,时间复杂度O(NlogN)
- 2.快速排序+遍历数组,时间复杂度为O(NlogN)+O(N)
- 3.快速搜索算法:时间复杂度为O(N)
此题我们采用快速搜索算法来解决问题
算法原理
快速搜索算法和快速排序的核心方法都是一致的,即分治法。因此它们的代码写起来会有很多相似一致。比如都要随机取key,也要划分数组。因此在这类已经在分治(1)讲过的内容,博主会简单带过。
第一步,我们可以随机取当前数组中的任意一个元素作为key值。并且将数组分为三部分,即x<key的部分,x=key的部分,x>key的部分(0<=x<=n-1)。关于划分数组的代码,可以参考上一篇文章颜色划分的代码。
完成这一步的数组将会是下面的形式:
我们假设这三部分的子数组的元素个数为a,b,c。
由于这个数组在经过一次划分之后,数组并非完全无序。而且是一个大体上升序的数组。因此,绿色部分(x>key)中的所有元素,都是原数组中前c个大的元素,蓝色部分的所有元素,都是原数组中前b+c个大的元素,而红色部分的所有元素,都是原数组中前a+b+c大的元素。
因此我们可以分成下面情况进行讨论:
- (1)若c>=k,则说明第k个大的数在绿色部分,我们可以继续用快速搜索算法来找到绿色部分的第k大的数。
- (2)若(1)不成立,且b+c>=k,则说明第k大的数在蓝色部分,由于蓝色部分的值都是固定的key,因此第k大的数就是key,将其返回即可。
- (3)若(1)、(2)不成立,且a+b+c>=k,则说明第k大的数在红色部分,由于红色部分之前的元素都是前b+c大的数,因此我们要在红色部分找第(k-b-c)大的数。对该部分继续使用快速搜索算法
题解代码
class Solution {
private:
void _swap(int& lhs,int& rhs){
int tmp=lhs;
lhs=rhs;
rhs=tmp;
}
int q_serch(vector<int>nums,int begin,int end,int k){
if(begin==end) return nums[begin];
int left=begin-1,right=end+1,i=begin;
int key=randomNum(nums,begin,end);
while(i<right){//将数组划分成三份
if(nums[i]<key) _swap(nums[i++],nums[++left]);
else if(nums[i]==key) i++;
else _swap(nums[i],nums[--right]);
}
int b=right-left-1,c=end-right+1;
if(c>=k) return q_serch(nums,right,end,k);//第k大的元素在绿色部分
else if(b+c>=k) return key;//第k大的元素在蓝色部分
else return q_serch(nums,begin,left,k-(b+c));//第k大的元素在红色部分
}
int randomNum(vector<int>nums,int begin,int end){//在nums的[begin,end]中随机一个元素作为key值
int keyi=rand()%(end-begin+1)+begin;
return nums[keyi];
}
public:
int findKthLargest(vector<int>& nums, int k) {
srand((unsigned int)time(nullptr));
return q_serch(nums,0,nums.size()-1,k);
}
};