LeeCode-刷题日记-Day33

215. 数组中的第K个最大元素

思路：堆排序，创建大顶堆。不用执行整个排序过程，即可完成拿到第k大值的目标。

每次将当前节点、左右子树的最大值拿出。递归调用即可拿出最大值。

只需要执行k次即可拿出前k大的值，剩下的就是目标值。

/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number}
 */
var findKthLargest = function(nums, k) {
    let heapSize=nums.length
    buildHeap(nums,heapSize);

    //进行下沉，大顶堆是最大元素下沉到末尾
    for(let i=nums.length-1;i>=nums.length-k+1;i--){
        //将最大元素放到末尾之后删除掉。最终在堆顶的就是目标元素
        swap(nums,0,i);
        --heapSize;
        maxHeap(nums,0,heapSize);
    }
    return nums[0];

    //自下而上构建一个大顶堆
    function buildHeap(nums,heapSize){
        for(let i=Math.floor(heapSize/2)-1;i>=0;i--){
            maxHeap(nums,i,heapSize);
        }
    }

    //从左向右，自上而下的调整节点
    function maxHeap(nums,i,heapSize){
        let l=i*2+1;//此处为当前节点左子树节点
        let r=i*2+2;//此处为当前节点右子树节点
        let largest=i;
        if(l<heapSize&&nums[l]>nums[largest])
            largest=l;
        if(r<heapSize&&nums[r]>nums[largest])
            largest=r;
        if(largest!==i){
            //当有左右子树的节点大于当前节点的值，交换节点
            swap(nums,i,largest);
            //遍历子树进行调整。
            maxHeap(nums,largest,heapSize);
        }
    }


    function swap(a,i,j){
        let temp=a[i];
        a[i]=a[j];
        a[j]=temp;
    }
};

347. 前 K 个高频元素

思路：

创建哈希表，将其出现次数和键值绑定。

按出现次数排序。并加入数组

从数组中切片，返回键值。

/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number[]}
 */
var topKFrequent = function(nums, k) {
    let map=new Map();
    for(let num of nums){
        map.set(num,map.has(num)?map.get(num)+1:1);
    }
    if(k===map.size) return [...map.keys()];
    let arr=Array.from(map).sort((a,b)=>{return b[1]-a[1]});
    return arr.splice(0,k).map(n=>n[0]);
};