215. 数组中的第K个最大元素
Opened this issue · 0 comments
webVueBlog commented
215. 数组中的第K个最大元素
Description
Difficulty: 中等
Related Topics: 数组, 分治, 快速选择, 排序, 堆(优先队列)
给定整数数组 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
Solution
Language: JavaScript
/**
* @param {number[]} nums
* @param {number} k
* @return {number}
*/
// 数组排序,取第 k 个数
// var findKthLargest = function (nums, k) {
// nums.sort((a, b) => b - a).slice(0, k)
// return nums[k - 1]
// };
// 构造前 k 个最大元素小顶堆,取堆顶
// 从数组中取出 k 个元素构造一个小顶堆,然后将其余元素与小顶堆对比,如果大于堆顶则替换堆顶,然后堆化,所有元素遍历完成后,堆中的堆顶即为第 k 个最大值
var findKthLargest = function (nums, k) {
let heap = [,], i = 0
while (i < k) {
heap.push(nums[i++])
}
buildHeap(heap, k)
for (let i = k; i < nums.length; i++) {
if (heap[1] < nums[i]) {
heap[1] = nums[i]
heapify(heap, k, 1)
}
}
return heap[1]
};
let buildHeap = (arr, k) => {
if (k === 1) return
for (let i = Math.floor(k/2); i>=1; i--) {
heapify(arr, k, i)
}
}
let heapify = (arr, k, i) => {
while(true) {
let minIndex = i
if (2*i <= k && arr[2*i] < arr[i]) {
minIndex = 2*i
}
if (2*i+1 <= k && arr[2*i+1] <arr[minIndex]) {
minIndex = 2*i + 1
}
if (minIndex !== i) {
swap(arr, i, minIndex)
i = minIndex
} else {
break
}
}
}
let swap = (arr, i, j) => {
let temp = arr[i]
arr[i] = arr[j]
arr[j] = temp
}