LeetCode215. 数组中的第K个最大元素🌟🌟🌟🌟中等
课后作业
问题描述
原文链接：215. 数组中的第K个最大元素
给定整数数组 nums 和整数 k，请返回数组中第 **k** 个最大的元素。
请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。
你必须设计并实现时间复杂度为 O(n) 的算法解决此问题。
示例 1:
输入: [3,2,1,5,6,4], k = 2
输出: 5
示例 2:
输入: [3,2,3,1,2,4,5,5,6], k = 4
输出: 4
提示：
1 <= k <= nums.length <= 105-104 <= nums[i] <= 104
代码实现
Java
class Solution {
public int findKthLargest(int[] nums, int k) {
// 默认是小根堆 复杂度 空间：O(k). 时间 nlogk
Queue<Integer> minQueue = new PriorityQueue<>();
for(int i = 0 ; i < nums.length; i++){
if(minQueue.size() < k){
minQueue.offer(nums[i]);
}else if(minQueue.peek() < nums[i]){
minQueue.poll();
minQueue.offer(nums[i]);
}
}
return minQueue.peek();
}
}
Python
import heapq
class Solution(object):
def findKthLargest(self, nums, k):
"""
:type nums: List[int]
:type k: int
:rtype: int
"""
# 默认是小根堆 复杂度 空间：O(k). 时间 nlogk
min_heap = []
for num in nums:
if len(min_heap) < k:
heapq.heappush(min_heap, num)
elif min_heap[0] < num:
heapq.heappushpop(min_heap, num)
return min_heap[0]
C++
class Solution {
public:
int findKthLargest(vector<int>& nums, int k) {
// 默认是小根堆 复杂度 空间：O(k). 时间 nlogk
std::priority_queue<int, std::vector<int>, std::greater<int>> min_heap;
for (int num : nums) {
if (min_heap.size() < k) {
min_heap.push(num);
} else if (min_heap.top() < num) {
min_heap.pop();
min_heap.push(num);
}
}
return min_heap.top();
}
};
Go
func findKthLargest(nums []int, k int) int {
// 默认是小根堆 复杂度 空间：O(k). 时间 nlogk
minHeap := &IntMinHeap{}
heap.Init(minHeap)
for _, num := range nums {
if minHeap.Len() < k {
heap.Push(minHeap, num)
} else if (*minHeap)[0] < num {
heap.Pop(minHeap)
heap.Push(minHeap, num)
}
}
return (*minHeap)[0]
}
type IntMinHeap []int
func (h IntMinHeap) Len() int { return len(h) }
func (h IntMinHeap) Less(i, j int) bool { return h[i] < h[j] }
func (h IntMinHeap) Swap(i, j int) { h[i], h[j] = h[j], h[i] }
func (h *IntMinHeap) Push(x interface{}) {
*h = append(*h, x.(int))
}
func (h *IntMinHeap) Pop() interface{} {
old := *h
n := len(old)
x := old[n-1]
*h = old[0 : n-1]
return x
}