Appearance
215. 数组中的第K个最大元素
题目描述
给定整数数组 nums 和整数 k，请返回数组中第 k 个最大的元素。
请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。
你必须设计并实现时间复杂度为 O(n) 的算法解决此问题。
示例 1:
[3,2,1,5,6,4],
示例 2:
[3,2,3,1,2,4,5,5,6],
**提示： **
1 <= k <= nums.length <= 105
-104 <= nums[i] <= 104
难度： Medium
题解代码
javascript
/**
* @param {number[]} nums
* @param {number} k
* @return {number}
*/
function findKthLargest (arr, k) {
const len = arr.length
for (let i = Math.floor(len / 2); i >= 0; i--) {
// 构建最大堆
maxHeapify(arr, i, len)
}
// 执行k-1次下沉
for (let j = 0; j < k - 1; j++) {
swap(arr, 0, len - 1 - j)
maxHeapify(arr, 0, len - 1 - j)
}
// 剩下的最大堆顶部为第k大的值
return arr[0]
}
function maxHeapify (arr, i, size) {
let l = i * 2 + 1
let r = i * 2 + 2
let largest = i
if (l < size && arr[l] > arr[largest]) {
largest = l
}
if (r < size && arr[r] > arr[largest]) {
largest = r
}
if (largest !== i) {
swap(arr, i, largest)
maxHeapify(arr, largest, size)
}
}
function swap (arr, i, j) {
[arr[i], arr[j]] = [arr[j], arr[i]]
}