215. 数组中的第K个最大元素

本文介绍: 思路：其中此思路是利用快排的思想，将整个数组划分为三大块，分别为大于 key 等于key和小于key这三大块！其中优先级队列利用的其实就是堆结构！建堆解决此问题的原理就是和优先级队列是一样的！算法思路和优先级队列一样，这里仅仅给出代码参考即可！不会的可以评论区继续讨论！因为是使用的优先级队列，所以要求第K个大的元素，只需要将数组POP （k-1）次，然后再取队列的队头元素即可！

题目：

解法一、优先级 队列

代码

#include&lt;queue&gt;
class Solution {
public:
    int findKthLargest(vector<int&gt;&amp; nums, int k)
    {
      //使用优先级队列直接秒杀！
      priority_queue<int ,vector<int>,less<int>> q;
        for(int i=0;i<nums.size();i++)
        {
            q.push(nums[i]);
        }
        int n=q.size();
        while(--k)
        {
            q.pop();
        }
        return q.top();
    }
};

思路：

因为是使用的优先级队列，所以要求第K个大的元素，只需要将数组POP （k-1）次，然后再取队列的队头元素即可！！

解法二：自己手撕堆结构，进行排序，然后取第k个元素即可！

其中优先级队列利用的其实就是堆结构！建堆解决此问题的原理就是和优先级队列是一样的！算法思路和优先级队列一样，这里仅仅给出代码参考即可！不会的可以评论区继续讨论！

#include<queue>
class Solution{
public:

void adjustdown(vector<int>&amp;arr,int n,int i)
{
    int child=i*2+1;
    while(child<n)
    {
        //建小堆！
        if(child+1<n &amp;&amp;arr[child]>arr[child+1])
        {
            child++;
        }
        if(arr[child]<arr[i])
        {
            swap(arr[child],arr[i]);
            i=child;
            child=i*2+1;
        }
        else
        {
            break;
        }
    }
}
    int findKthLargest(vector<int>&amp; nums, int k)
    {
        //首先进行建堆！
        int n=nums.size();
        for(int i=(n-1-1)/2;i>=0;i--)
        {
            adjustdown(nums,n,i);
        }
        int end = n - 1;
        while (end >0)
        {
        swap(nums[0], nums[end]);
        adjustdown(nums, end, 0);
        --end;
        }
        return nums[k-1];
    }
};

解法三、基于快排的快速 选择！

代码：

class Solution {
public:

    int getkey(vector<int>&amp;nums,int left,int right)
    {
        int r=rand();
        return nums[r%(right-left+1)+left];
    }
    int qsort(vector<int>&amp;nums,int left,int right,int k)
    {
        int l=-1,r=right+1;
        int i=0;
        int key=getkey(nums,left,right);
        while(i<r)
        {
            if(nums[i]<key)
            {
                swap(nums[++l],nums[i++]);
            }
            else if(nums[i]>key)
            {
                swap(nums[--r],nums[i]);
            }
            else
            {
                i++;
            }
        }

        int a=l-left+1;
        int b=r-l-1;
        int c=right-r+1;

        if(c>=k)
        {
            return qsort(nums,r,right,k);
        }
        else if(b+c>=k)
        {
            return key;
        }
        else
        {
            return qsort(nums,left,l,k-b-c);
        }
        return 0;
    }
    int findKthLargest(vector<int>&amp; nums, int k) 
    {
            srand(time(NULL));
            //基于快排的优化求topk问题！
            int n=nums.size()-1;
            int s=qsort(nums,0,n,k);
            return s; 
    }
};