题目描述
给你一个整数数组 nums
和一个整数 k
,请你返回其中出现频率前 k
高的元素。你可以按 任意顺序 返回答案。
示例 1:
输入: nums = [1,1,1,2,2,3], k = 2
输出: [1,2]
示例 2:
输入: nums = [1], k = 1
输出: [1]
提示:
1 <= nums.length <= 105
k
的取值范围是[1, 数组中不相同的元素的个数]
- 题目数据保证答案唯一,换句话说,数组中前
k
个高频元素的集合是唯一的
进阶: 你所设计算法的时间复杂度 必须 优于 O(n log n)
,其中 n
**是数组大小。
分析解答
相同元素都对应一个出现次数,可以很容易想到 map。key, value 代表元素和出现的次数。
然后就可以不断(k 次)遍历 比较 value,并把 key 加入结果数组中。
/**
* @param {number[]} nums
* @param {number} k
* @return {number[]}
*/
var topKFrequent = function(nums, k) {
let map = new Map()
let res = []
for (let i = 0; i < nums.length; i++) {
if (!map.has(nums[i])) {
map.set(nums[i], 1)
} else {
map.set(nums[i], map.get(nums[i]) + 1)
}
}
for (let i = 0; i < k; i++) {
let maxValue = -999
let maxIndex = -999
for (let j of map.keys()) {
if (map.get(j) > maxValue) {
maxValue = map.get(j)
maxIndex = j
}
}
res.push(maxIndex)
map.delete(maxIndex)
}
return res
};
let nums = [1,1,1,2,2,3], k = 2
console.log(topKFrequent(nums, k))
思路拓展
这里使用优先级队列来解决。
/**
* @param {number[]} nums
* @param {number} k
* @return {number[]}
*/
var topKFrequent = function(nums, k) {
const map = new Map();
for(const num of nums) {
map.set(num, (map.get(num) || 0) + 1);
}
// 创建小顶堆
const priorityQueue = new PriorityQueue((a, b) => a[1] - b[1]);
// entry 是一个长度为2的数组,0位置存储key,1位置存储value
for (const entry of map.entries()) {
priorityQueue.push(entry);
if (priorityQueue.size() > k) {
priorityQueue.pop();
}
}
const ret = [];
for(let i = priorityQueue.size() - 1; i >= 0; i--) {
ret[i] = priorityQueue.pop()[0];
}
return ret;
};
function PriorityQueue(compareFn) {
this.compareFn = compareFn;
this.queue = [];
}
// 添加
PriorityQueue.prototype.push = function(item) {
this.queue.push(item);
let index = this.queue.length - 1;
let parent = Math.floor((index - 1) / 2);
// 上浮
while(parent >= 0 && this.compare(parent, index) > 0) {
// 交换
[this.queue[index], this.queue[parent]] = [this.queue[parent], this.queue[index]];
index = parent;
parent = Math.floor((index - 1) / 2);
}
}
// 获取堆顶元素并移除
PriorityQueue.prototype.pop = function() {
const ret = this.queue[0];
// 把最后一个节点移到堆顶
this.queue[0] = this.queue.pop();
let index = 0;
// 左子节点下标,left + 1 就是右子节点下标
let left = 1;
let selectedChild = this.compare(left, left + 1) > 0 ? left + 1 : left;
// 下沉
while(selectedChild !== undefined && this.compare(index, selectedChild) > 0) {
// 交换
[this.queue[index], this.queue[selectedChild]] = [this.queue[selectedChild], this.queue[index]];
index = selectedChild;
left = 2 * index + 1;
selectedChild = this.compare(left, left + 1) > 0 ? left + 1 : left;
}
return ret;
}
PriorityQueue.prototype.size = function() {
return this.queue.length;
}
// 使用传入的 compareFn 比较两个位置的元素
PriorityQueue.prototype.compare = function(index1, index2) {
if (this.queue[index1] === undefined) {
return 1;
}
if (this.queue[index2] === undefined) {
return -1;
}
return this.compareFn(this.queue[index1], this.queue[index2]);
}