分治（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);
    }
};