题目
215. 数组中的第K个最大元素
给定整数数组 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
我的代码（Python）
version I
/**
* @param {number[]} nums
* @param {number} k
* @return {number}
*/
var findKthLargest = function(nums, k) {
let lessArray = [];
let biggerArray = [];
let comparator = nums[nums.length - k];
for (let i = 0; i < nums.length; i++) {
if (i === nums.length - k) {
continue;
}
if (nums[i] >= comparator) {
biggerArray.push(nums[i]);
} else {
lessArray.push(nums[i]);
}
}
console.log(nums);
console.log(k);
console.log(comparator);
console.log(biggerArray);
console.log(lessArray);
if (biggerArray.length == k - 1) {
return comparator;
} else if (biggerArray.length > k - 1) {
lessArray = [];
return findKthLargest(biggerArray, k);
} else {
let newTar = k - 1 - biggerArray.length;
biggerArray = [];
return findKthLargest(lessArray, newTar);
}
};类似快排，但是会超出memory。如果K是常数，这倒是可以O(n)级别。
version II
/**
* @param {number[]} nums
* @param {number} k
* @return {number}
*/
class MyMinHeap {
constructor(k) {
this.maxCnt = k;
this.count = 0;
this.min = 0;
this.saveMap = new Map();
}
insert(val) {
if (this.count == 0) {
this.min = val;
this.saveMap.set(val, 1);
this.count++;
} else if (this.count < this.maxCnt) {
if (this.saveMap.has(val)) {
this.saveMap.set(val, this.saveMap.get(val) + 1);
} else {
this.saveMap.set(val, 1);
this.min = Math.min(this.min, val);
}
this.count++;
} else {
if (val > this.min) {
if (this.saveMap.has(val)) {
this.saveMap.set(val, this.saveMap.get(val) + 1);
} else {
this.saveMap.set(val, 1);
this.min = Math.min(this.min, val);
}
let minCnt = this.saveMap.get(this.min);
if (minCnt > 1) {
this.saveMap.set(this.min, minCnt - 1);
} else {
this.saveMap.delete(this.min);
this.min = val;
for (const key of this.saveMap.keys()) {
this.min = Math.min(this.min, key);
}
}
}
}
}
getMin() {
return this.min;
}
}
var findKthLargest = function(nums, k) {
let minHeap = new MyMinHeap(k);
for (const num of nums) {
minHeap.insert(num);
}
return minHeap.getMin();
};自己写了个简化版本的最小堆，依然超时，应该是每次插入后找最小值遍历效率很差。
点评
应该可以优化第一个方法，转成循环方式，或者不要创建新的列表存储，在原地处理，存储会优化。
感觉思路被限制住了，一直在想如何处理数据结构，没有跳出来。
花费了太多时间，所以放弃了直接看答案……
官方解答第一个方法就是我所想的第一个解法的优化。
第二个是实现一个最小堆。
所以我的思路倒是对的……
baddif@gmail.com
AI简历优化站
AI求职跟踪器（建设中）
主站（建设中）
相关平台
Github Issues / Notion / Blog