[数据结构与算法]数组中的第k个最大元素(堆)

    科技2022-09-03  104

    在未排序的数组中找到第 k 个最大的元素。请注意,你需要找的是数组排序后的第 k 个最大的元素,而不是第 k 个不同的元素。

    示例 1: 输入: [3,2,1,5,6,4] 和 k = 2 输出: 5 示例 2: 输入: [3,2,3,1,2,4,5,5,6] 和 k = 4 输出: 4

    说明:

    你可以假设 k 总是有效的,且 1 ≤ k ≤ 数组的长度。

    来源:力扣(LeetCode) 链接:https://leetcode-cn.com/problems/kth-largest-element-in-an-array

    解题:(利用最小堆)

    // 引入堆数据结构,具体实现参考https://blog.csdn.net/qq_43540219/article/details/108932367 var findKthLargest = function (nums, k) { const h = new MinHeap() nums.forEach(n => { h.insert(n) if (h.size() > k) { h.pop() } }) return h.peek() }

    时间复杂度O(nlogk) // insert 和 pop的复杂度是logk

    Processed: 0.008, SQL: 9