【数据结构与算法】力扣 347. 前 K 个高频元素

本文主要是介绍【数据结构与算法】力扣 347. 前 K 个高频元素，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目描述

给你一个整数数组 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 = -999let maxIndex = -999for (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))

思路拓展

这里使用优先级队列来解决。

【数据结构与算法】堆 - 掘金 (juejin.cn)

/*** @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位置存储valuefor (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]);
}