数组中的第K个最大元素

发表于 分类于 阅读次数：

数组中的第K个最大元素（难度：中等）

3

方法一：排序

先对数组进行排序，再返回倒数第 k 个元素。

复杂度

时间复杂度：O(nlogn)

空间复杂度：O(1)

这个时间复杂度并不令人满意

代码
1
2
3
4
class Solution:
    def findKthLargest(self, nums: List[int], k: int) -> int:
        nums.sort()
        return nums[-k]
1

方法二：最小堆

建一个只能存K个数字的小顶堆，超过K时候，每加进来一个，堆顶就要弹出一个。数组遍历完，最终堆顶的元素就是第K大的（堆里其他元素都比它还要大）。

复杂度

时间复杂度：O(nlogk). 向大小为 k 的堆中添加元素的时间复杂度为O(logk)，我们将重复该操作 n 次，故总时间复杂度为O(nlogk)。

空间复杂度：O(k).

代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
    public int findKthLargest(int[] nums, int k) {
        PriorityQueue<Integer> minHeap = new PriorityQueue<>();

        for(int num : nums){
            minHeap.add(num);
            if(minHeap.size()>k)
                minHeap.poll();
        }

        return minHeap.poll();
        
    }
}
2

方法三：快速选择

详见这里.

复杂度

时间复杂度 : 平均情况O(N)，最坏情况 O(N^2)。

空间复杂度 : O(1)。