寻找第K大小顶堆priority_queue

题目描述有一个整数数组请你根据快速排序的思路找出数组中第K大的数。给定一个整数数组a,同时给定它的大小n和要找的K(K在1到n之间)请你根据快速排序的思路找出数组中第K大的数。

给定一个整数数组a,同时给定它的大小n和要找的K(K在1到n之间)请返回第K大的数保证答案存在。

示例1

输入

[1,3,5,2,2],5,3

返回值

2

题目链接寻找第K大_牛客题霸_牛客网

这题我按照这篇博客寻找数组中第K大的数时间复杂度O(N)提到的3种方法都试一下

方法1

对数组A进行排序然后遍历一遍就可以找到第K大的数字。该方法的时间复杂度为O(N*logN)

class Solution {public:int findKth(vector a, int n, int K) {// write code heresort(a.begin(),a.end());return a[n-K];}};

 方法2

利用简单选择排序法的思想每次通过比较选出最大的数字来比较上K次就能找出第K大的数字来。该方法的时间复杂度为O(N*K)最坏情况下为O(N^2)。

class Solution {public:void selectK(vector a.size(),index0;for(int i0;i方法3

利用快排的思想首先快排每次执行都能确定一个元素的最终的位置如果这个位置是n-k(其中n是数组A的长度)的话那么就相当于找到了第K大的元素。设确定的元素位置m的话如果m > n - k大的话那么第K大的数字一定在A[0]~A[m - 1]之间如果m

class Solution {public:int Partition(vector a[low];while(lown-K){highpos-1;posPartition(a, low, high);}else{lowpos1;posPartition(a, low, high);}}return a[n-K];}};

方法4

小顶堆

class Solution {public:int findKth(vector a, int n, int K) {// write code hereint ans0;priority_queue que;//小顶堆维护前K大的数for(int i0;i que.top()){que.pop();que.push(a[i]);}}}return que.top();}};