如何构建第K大小元素的优先队列？

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

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

具体要求：

1.给定一个整数数组a。

2.同时给定它的大小n和要找的K（K的范围是1到n之间）。

3.根据快速排序的思想，找出数组中第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大的数字来。该方法的时间复杂度为O(N*K)最坏情况下为O(N^2)。