在做题中学习（78）：数组中第K个最大元素

解法：快速选择算法

说明：堆排序也是经典解决topK问题的算法，但时间复杂度为：O(NlogN)

而将要介绍的快速选择算法的时间复杂度为: O(N)

先看我的前两篇文章，分别学习：数组分三块，随机选择基准值的思想。会的话直接看就完事了

思路：

解惑：

1.a,b,c是什么意思？

        a,b,c分别是<key, = key, >key 所代表的区间中值的个数

2.如何判断？

        看落在哪个区间，c区间全是>key的，所以如果落在这个区间，就只在这个区间递归即可。

        而如果 b + c >=k 说明，k > c了也就是不在c区间，而第k个元素是在b这个区间中，而b是= key的，所以直接返回key即可。

        如果都不是，说明k > b + c了，所以k是很大的数字，那第k大就是一个很小的数字，肯定落在a区间，而因为现在我们跳过了 b+c个元素，所以要找的其实是第k - b - c个元素！

附上完整代码：

class Solution {
public:

    int findKthLargest(vector<int>& nums, int k) 
    {
        srand(time(nullptr));
        return qselect(nums,0,nums.size()-1,k);
    }

    int qselect(vector<int>& nums,int l,int r,int k)
    {
        //返回条件
        if(l >= r)
            return nums[l];
        //选择基准元素
        int key = GetRandomKey(nums,l,r);
        int left = l-1,right = r+1;
        //快排（数组分三块）的一趟
        for(int i = l;i<nums.size();)
        {
            if(nums[i] < key)
                swap(nums[++left],nums[i++]);
            else if(nums[i] == key)
                i++;
            else if(nums[i] > key)
            {
                if(i == right)
                    break;
                swap(nums[--right],nums[i]);
            }
        }
        //分情况讨论
        int c = r - right + 1,b = right - left - 1;
        if(c >= k) 
            return qselect(nums,right,r,k);
        else if(b + c >= k) 
            return key;
        else    
            return qselect(nums,l,left,k-b-c);
    }
    int GetRandomKey(vector<int>& nums,int l,int r)
    {
        int randnum = rand();
        return nums[randnum % (r - l + 1) + l];
    }
};

原文地址：https://blog.csdn.net/yiren_liusong/article/details/144318108

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！