做网站有2个前提条件_一个是网站,wordpress付费主题博客,珠海网站建设排名,菜鸟教程网页制作模板数组中的第K个最大元素
https://leetcode.cn/problems/kth-largest-element-in-an-array/
描述
给定整数数组 nums 和整数 k#xff0c;请返回数组中第 k 个最大的元素。请注意#xff0c;你需要找的是数组排序后的第 k 个最大的元素#xff0c;而不是第 k 个不同的元素。…数组中的第K个最大元素
https://leetcode.cn/problems/kth-largest-element-in-an-array/
描述
给定整数数组 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 1 0 5 10^5 105- 1 0 4 10^4 104 nums[i] 1 0 4 10^4 104
算法实现
1 基于js中原生sort api
const findKthLargest function(nums, k) {return nums.sort((a,b) b-a)[k - 1]
};这个浏览器默认提供的sort()方法一般时间复杂度是 O(nlogn)
2 基于堆的数据结构和堆排序的方法
// 建立最小堆类
class MinHeap {heap: number[] [];// 交换节点位置swap(i, j) {[this.heap[i], this.heap[j]] [this.heap[j], this.heap[i]];}// 获得父节点getParentIndex(i) {return (i - 1) 1;}// 获取左子节点getLeftIndex(i) {return (i 1) 1; // 极客写法}// 获取右子节点getRightIndex(i) {return (i 1) 2;}// 向上移动shiftUp(index) {// 如果到了堆顶元素index是0则不要再上移了if(!index) return;const parentIndex this.getParentIndex(index)if(this.heap[parentIndex] this.heap[index]) {this.swap(parentIndex, index)this.shiftUp(parentIndex)}}// 下移shiftDown(index) {// 边界1如果到了堆尾元素则不要再下移了if(index this.heap.length - 1) return;const size this.size();const leftIndex this.getLeftIndex(index);const rightIndex this.getRightIndex(index);if (leftIndex size this.heap[leftIndex] this.heap[index]) {this.swap(leftIndex, index);this.shiftDown(leftIndex);}if (rightIndex size this.heap[rightIndex] this.heap[index]) {this.swap(rightIndex, index);this.shiftDown(rightIndex);}}// 插入insert(value) {this.heap.push(value);this.shiftUp(this.heap.length - 1);}// 删除堆顶pop() {// pop()方法删除数组最后一个元素并返回赋值给堆顶this.heap[0] this.heap.pop();// 对堆顶重新排序this.shiftDown(0);}// 获取堆顶peak() {return this.heap[0];}// 获取堆的大小size() {return this.heap.length;}
}// 实现
const findKthLargest (nums, k) {const h new MinHeap();nums.forEach(n {// 将数组元素依次插入堆中h.insert(n);// 如果堆满则执行优胜劣汰(h.size() k) h.pop();})// 返回堆顶此时就是第k大的元素return h.peak();
};关键在于这个堆的数据结构提供的 insert 方法 与 pop 方法时间复杂度O(nlogk) 一个n循环里面还嵌套一个heap的上移递归操作logk总体n*logk 空间复杂度: O(k) 或 O(logn) 堆的大小数组的大小, k是输入的堆大小 注意 本题使用的是一个堆排序的算法O(nlogn)但是还有其他排序也可以达到这个效率但是这个不符合题目的要求时间复杂度为 O(n) 的算法
3 基于快速排序
TODO
