网络异常，图片无法展示
|
「这是我参与11月更文挑战的第10天，活动详情查看：2021最后一次更文挑战」
给你一个整数数组 nums 和一个整数 k ，请你返回其中出现频率前 k 高的元素。你可以按 任意顺序 返回答案。
示例 1:
输入: nums = [1,1,1,2,2,3], k = 2 输出: [1,2] 复制代码
示例 2:
输入: nums = [1], k = 1 输出: [1] 复制代码
提示：
1 <= nums.length <= 105k的取值范围是[1, 数组中不相同的元素的个数]- 题目数据保证答案唯一，换句话说，数组中前
k个高频元素的集合是唯一的
进阶： 你所设计算法的时间复杂度 必须 优于 O(n log n) ，其中 n **是数组大小。
本题需要找到前 k 个高频元素，通常维护前 k 个最值的问题，都可以通过堆来解决
堆的性质
网络异常，图片无法展示
|
堆的插入
插入堆就是在数组的末尾插入元素
然后判断新插入元素是否影响了当前三元组的平衡。以大顶堆为例，如果插入元素的值大于根节点的值，则交换两个节点，直到新插入元素所在三元组满足根节点的值为当前三元组最值为止
堆的弹出
堆的弹出操作指弹出堆顶元素，对应数组下标 0 的元素，此时更新数组末尾元素为数组第一个元素，并删除之前末尾元素
然后判断新的堆顶元素是否影响了当前三元组的平衡。以大顶堆为例，如果新的堆顶元素不是当前三元组最大值，则与当前三元组最大值进行交换，知道它成为新的三元组的最大值为止
题解1
理解了堆的性质，我们来看一下本题的第一种题解
- 使用
map维护数组中元素的值以及出现的次数 - 创建一个小顶堆用来维护前
k个高频元素 - 遍历
map,如果堆中的元素大于等于k个，并且堆顶元素大于本次循环数据的val值，不进行插入，否则本次循环数据插入堆中 - 当堆不为空的时候，将堆顶元素弹出，把弹出值的
key放到结果数组中，最后返回结果数组即可
代码如下：
class MinHeap { constructor(max){ this.arr = []; this.size = 0; this.max = max; } // 插入元素 push(val){ this.arr.push(val); this.size++; if(this.size>1){ let cur = this.size-1, parentInd = (cur-1)>>1; while(cur>0 && this.arr[parentInd].val>this.arr[cur].val){ [this.arr[parentInd],this.arr[cur]] = [this.arr[cur],this.arr[parentInd]] cur = parentInd; parentInd = (cur-1)>>1; } } while(this.size>this.max) this.pop(); } // 弹出堆顶元素 pop(){ if(this.empty()) return false; const res = this.arr[0] this.arr[0] = this.arr.pop(); this.size--; let cur = 0, childl = 1, childr = 2; while( (childl<this.size&&this.arr[childl].val<this.arr[cur].val) || (childr<this.size&&this.arr[childr].val<this.arr[cur].val) ){ if(childr<this.size&&this.arr[childr].val<this.arr[childl].val){ [this.arr[cur],this.arr[childr]] = [this.arr[childr],this.arr[cur]] cur = childr; }else{ [this.arr[cur],this.arr[childl]] = [this.arr[childl],this.arr[cur]] cur = childl; } childl =cur*2+1,childr = cur*2+2; } return res; } // 判断堆是否为空 empty(){ return this.size === 0 } // 返回堆顶元素 top(){ return this.arr[0] } } var topKFrequent = function(nums, k) { // map 维护数组中的值以及出现的次数 const map = new Map(); for(let i = 0;i<nums.length;i++){ const cur = nums[i] if(map.has(cur)){ map.set(cur,map.get(cur)+1) }else{ map.set(cur,1) } } // 创建小顶堆维护前k个高频元素 const heap = new MinHeap(k); map.forEach((val,key) => { if(heap.size<k || heap.top().val<val){ heap.push({val,key}) } }) // 将堆中元素放入结果数组 const ret = []; while(!heap.empty()){ ret.push(heap.pop().key) } return ret; }; 复制代码
题解2
- 使用
map维护数组中元素的值以及出现的次数 - 通过
Array.from将map转为数组 - 根据元素出现的次数进行降序排序
- 将前k个高频元素的值放到结果数组
代码如下：
var topKFrequent = function(nums, k) { // map 维护数组中的值以及出现的次数 const map = new Map(); for(let i = 0;i<nums.length;i++){ const cur = nums[i] if(map.has(cur)){ map.set(cur,map.get(cur)+1) }else{ map.set(cur,1) } } // 将map转为数组 const arr = Array.from(map); // 根据元素出现的次数进行降序排序 arr.sort((a,b) => b[1]-a[1]) // 将前k个高频元素的值放到结果数组 const ret = []; for(let i = 0;i<k;i++){ ret.push(arr[i][0]) } return ret; }; 复制代码
至此，我们就通过两种方式完成了 leetcode-347-前K个高频元素
如有任何问题或建议，欢迎留言讨论！
