题目
给你一个整数数组 nums 和一个整数 k ，请你返回其中出现频率前 k 高的元素。你可以按 任意顺序 返回答案。
示例 1：
输入：nums = [1,1,1,2,2,3], k = 2
输出：[1,2]
示例 2：
输入：nums = [1], k = 1
输出：[1]
示例 3：
输入：nums = [1,2,1,2,1,2,3,1,3,2], k = 2
输出：[1,2]
提示：
- 1 <= nums.length <= 105
- k 的取值范围是 [1, 数组中不相同的元素的个数]
- 题目数据保证答案唯一，换句话说，数组中前 k 个高频元素的集合是唯一的
进阶：你所设计算法的时间复杂度 必须 优于 O(n log n) ，其中 n 是数组大小。
我的代码（Python）
/**
* @param {number[]} nums
* @param {number} k
* @return {number[]}
*/
var topKFrequent = function(nums, k) {
let cntMap = new Map();
for (let num of nums) {
if (cntMap.has(num)) {
cntMap.set(num, cntMap.get(num) + 1);
} else {
cntMap.set(num, 1);
}
}
// console.log(cntMap);
class HeapNode {
constructor(cnt, val) {
this.cnt = cnt;
this.val = val;
}
}
class MyKMinHeap {
constructor(k) {
this.maxCnt = k;
this.numList = [];
}
bubbleUp() {
let idx = this.numList.length - 1;
let parentIdx = Math.floor((idx - 1) / 2);
while (parentIdx < idx && parentIdx >= 0 &&this.numList[idx].cnt < this.numList[parentIdx].cnt) {
let tmp = this.numList[idx];
this.numList[idx] = this.numList[parentIdx];
this.numList[parentIdx] = tmp;
idx = parentIdx;
parentIdx = Math.floor((idx - 1) / 2);
}
}
sink() {
let idx = 0;
let lChild = idx * 2 + 1;
let rChild = idx * 2 + 2;
// console.log("numList: " + this.numList);
// console.log(lChild);
// console.log(this.numList[lChild]);
// console.log(rChild);
// console.log(this.numList[rChild]);
while ((lChild < this.numList.length && this.numList[idx].cnt > this.numList[lChild].cnt) || (rChild < this.numList.length && this.numList[idx].cnt > this.numList[rChild].cnt)) {
let toBeChanged = lChild;
if (lChild < this.numList.length && rChild < this.numList.length) {
if (this.numList[lChild].cnt > this.numList[rChild].cnt) {
toBeChanged = rChild;
}
}
let tmp = this.numList[toBeChanged];
this.numList[toBeChanged] = this.numList[idx];
this.numList[idx] = tmp;
idx = toBeChanged;
lChild = idx * 2 + 1;
rChild = idx * 2 + 2;
// console.log('idx: ' + idx + ", lChild: " + lChild + ", rChile: " + rChild);
}
}
insert(cnt, val) {
// console.log('cnt: ' + cnt + ", val: " + val);
if (this.numList.length == k) {
if (cnt <= this.numList[0].cnt) {
return false;
}
this.extractMin();
}
this.numList.push(new HeapNode(cnt, val));
this.bubbleUp();
return true;
}
extractMin() {
this.numList[0] = this.numList[this.numList.length - 1];
this.numList.pop();
this.sink();
}
}
let myHeap = new MyKMinHeap(k);
cntMap.forEach((value, key) => {
myHeap.insert(value, key);
// console.log(myHeap.numList);
});
let result = [];
for (let heapNode of myHeap.numList) {
result.push(heapNode.val);
}
return result;
};点评
经过上一题目的洗礼，215. 数组中的第K个最大元素，我的解法这里最终还是实现了一个最小堆来处理。
不过理论上这个时间复杂度仍然是O(nlogn)才对……
官方的第一个方法也是如此。
第二个解法的方向当时我想了一下，没深入，因为觉得时间复杂度不会变，所以回来实现堆来解题，看来还是直观印象不正确。
baddif@gmail.com
AI简历优化站
AI求职跟踪器（建设中）
主站（建设中）
相关平台
Github Issues / Notion / Blog