如何将寻找第K大小顶堆的priority_queue改写为长尾？

本文共计608个文字，预计阅读时间需要3分钟。

题目描述：给定一个整数数组，请根据快速排序的思想找出数组中第K大的数。

给定一个整数数组a，同时定义它的大小n和要找的第K大的数K（K的范围为1到n之间），请根据快速排序的思想找出数组中第K大的数。

题目描述有一个整数数组请你根据快速排序的思路找出数组中第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大的数字来。