每日算法：前K个高频元素

给定一个非空整数数组，返回前k个最常出现的元素。示例1：输入：nums=[1,1,1,2,2,3],k=2输出：[1,2]示例2：输入：nums=[1],k=1输出：[1]提示：你可以假设给定的k总是合理的，并且1≤k≤数组中不同元素的数量。您的算法的时间复杂度必须优于O(nlogn)，其中n是数组的大小。题目数据保证答案唯一，即数组中前k个高频元素的集合唯一。您可以按任何顺序返回答案。方案一：map+array用map记录每个元素出现的频率，用array对元素进行比较排序代码实现：lettopKFrequent=function(nums,k){letmap=newMap(),arr=[...newSet(nums)]nums.map((num)=>{if(map.has(num))map.set(num,map.get(num)+1)elsemap.set(num,1)})returnarr。sort((a,b)=>map.get(b)-map.get(a)).slice(0,k);};复杂度分析：时间复杂度：O(nlogn)空间复杂度：O(n)题目要求算法的时间复杂度必须优于O(nlogn)，所以这个实现不符合题目要求方案二：map+小顶堆遍历数组统计每个元素出现的频率，比较元素值（key）与出现的频率（value）存入map，构造第一个的小顶堆k个高频元素通过地图数据。小顶堆上任一节点的值必须小于等于其左右子节点的值，即堆顶为最小值。具体步骤如下：遍历数据，统计每个元素出现的频率，将元素值（key）和出现频率（value）保存在map中遍历map，从k位开始构造一个小顶堆，继续遍历map，将每条数据的出现频率与小顶堆堆顶元素的出现频率进行比较。如果小于堆顶元素，什么也不做，继续遍历下一个元素；如果大于堆顶元素，则将此元素替换堆顶元素，然后堆成小堆顶。遍历完成后heap中的数据为topk数据代码实现：lettopKFrequent=function(nums,k){letmap=newMap(),heap=[,]nums.map((num)=>{if(map.has(num))map.set(num,map.get(num)+1)elsemap.set(num,1)})//如果元素个数小于等于kif(map.size<=k){return[...map.keys()]}//如果元素个数大于k，则遍历map，建立小顶堆leti=0map.forEach((value,key)=>{if(i{if(k===1)return//从最后一个非叶子节点开始，自上而下堆for(leti=Math.floor(k/2);i>=1;i--){heapify(heap,map,k,i)}}//heapify=(heap,map,k,i)=>{//top-向下堆化while(true){letminIndex=iif(2*i<=k&&map.get(heap[2*i]){if(map.has(num))map.set(num,map.get(num)+1)elsemap.set(num,1)})//如果元素个数小于等于kif(map.size<=k){return[...map.keys()]}returnbucketSort(map,k)};//桶排序letbucketSort=(map,k)=>{letarr=[],res=[]map.forEach((value,key)=>{//利用映射关系（以出现频率为下标）将数据分布到各个桶中if(!arr[value]){arr[value]=[key]}else{arr[value].push(key)}})//倒序遍历得到出现频率最高的前k个数for(leti=arr.length-1;i>=0&&res.length