leetcode 215题 数组中的第K个最大元素
给定整数数组 nums 和整数 k，请返回数组中第 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
示例 3：
输入：nums = [0]
输出：0
思路
方法一： 排序 方法二：最小堆
代码
// sort
var findKthLargest = function(nums, k) {
// 先排序，再查找
nums.sort((a, b) => a - b);
return nums[nums.length - k];
};
// minheap
function findKthLargest(nums, k) {
// 利用最小堆，堆顶元素小于左右节点，不断返回堆顶的元素，只需要返回 nums.length - k 次
const minHeap = new MinHeap();
const heap = minHeap.build(nums);
for (let i=0; i<nums.length - k; i++) {
minHeap.exectHeap();
}
return heap[1];
}
class MinHeap {
constructor() {
this.data = [null];
}
build(nums) {
nums.forEach((num, index) => {
this.insert(num);
});
return this.data;
}
exectHeap() {
const val = this.data.pop();
this.data[1] = val;
this.heapDown(1);
return val;
}
insert(val) {
this.data.push(val);
this.heapUp(this.data.length - 1);
}
heapUp(index) {
let pIndex = index >> 1;
while (pIndex > 0) {
const lIndex = pIndex * 2;
const rIndex = lIndex + 1;
let minIndex = lIndex;
if (this.data[minIndex] > this.data[rIndex]) {
minIndex = rIndex;
}
if (this.data[pIndex] > this.data[minIndex]) {
this.swap(this.data, pIndex, minIndex);
}
pIndex = pIndex >> 1;
}
}
heapDown(index) {
while (index > 0 && this.data[index*2]) {
const lIndex = index * 2;
const rIndex = lIndex + 1;
let minIndex = lIndex;
if (this.data[lIndex] > this.data[rIndex]) {
minIndex = rIndex;
}
if (this.data[index] > this.data[minIndex]) {
this.swap(this.data, index, minIndex);
}
index = minIndex;
}
}
swap(data, i, j) {
[data[i], data[j]] = [data[j], data[i]];
}
}
复杂度分析
方法一：
- 时间复杂度：O(N)
- 空间复杂度：O(1)
方法二：
- 时间复杂度：O(logN)
- 空间复杂度：O(N)