【Leetcode】347. 前 K 个高频元素_前k个高频元素 这个题什么意思

题目链接：347. Top K Frequent Elements

题目内容：给你一个整数数组 nums 和一个整数 k ，请你返回其中出现频率前 k 高的元素。你可以按 任意顺序 返回答案。

思路：就是统计每一个数字出现的次数，然后找到出现次数前k大的k个元素。统计数字出现的次数可以用哈希表。然后问题就转换成了求n个数中前k大的k个数。

方法一：k个元素的小端堆

遍历数组nums，放入哈希表中，map<key,value>，key是数据，value是出现的次数。

将map中的key-value对放入数组中，构成一个二维数组entrys。

假设不同的数字一共有n个，entrys的长度就是n。就是求n个数中value最大的前k个数。

建立一个长度为k的小端堆，先用entrys中的前k个元素创建小端堆，堆顶元素是k个元素中value值最小的。然后依次遍历剩下的entrys[k]到entrys[n-1]。

如果遍历到的entrys[i]的value值小于堆顶元素的value，那么至少有k个元素的value比entrys[i]更大，不进行任何操作。如果大于堆顶元素的value，那么也说明至少有k个元素的value比堆顶元素的value大，那么就和堆顶元素进行交换，继续调整小端堆。

这样遍历完之后就能保证小端堆中的k个数value值就是最大的。得到了前k大的数。

js代码如下：

var topKFrequent2 = function (nums, k) {
    // 堆排序
    function heapMinSort(nums, k) {
        function heapInsert(nums, i) {
            if (i == 0)
                return;
            let fi = Math.floor((i - 1) / 2);
            if (nums[i][1] >= nums[fi][1])
                return;
            else {
                let temp = nums[i];
                nums[i] = nums[fi];
                nums[fi] = temp;
                heapInsert(nums, fi);
            }
        }
        // 调整堆
        function heapify(nums, i, end) {
            let li = 2 * i + 1;
            let ri = 2 * i + 2;
            let index;
            if (li > end)
                return;
            else if (ri > end)
                index = li;
            else
                index = nums[li][1] < nums[ri][1] ? li : ri;
            if (nums[index][1] < nums[i][1]) {
                let temp = nums[index];
                nums[index] = nums[i];
                nums[i] = temp;
                heapify(nums, index, end);
            }
        }
        const length = nums.length;
        // 创建初始堆,只有k个元素的小端堆
        for (let i = 0; i < k; i++) {
            heapInsert(nums, i);
        }
        // 调整  保证前k个元素最大
        for (let i = k; i < length; i++) {
            if (nums[i][1] <= nums[0][1])
                continue;
            else {
                let temp = nums[0];
                nums[0] = nums[i];
                nums[i] = temp;
                heapify(nums, 0, k-1);
            }
        }
    }
    let map = new Map();
    const length = nums.length;
    // 哈希表是一定要用的O(n)
    for (let i = 0; i < length; i++) {
        if (map.has(nums[i]))
            map.set(nums[i], map.get(nums[i]) + 1);
        else
            map.set(nums[i], 1);
    }
 
    let entryArr = new Array();
    for (const entry of map) {
        entryArr.push(entry);
    }
    heapMinSort(entryArr, k);
    let resArr = new Array();
    for (let i = 0; i < k; i++) {
        resArr.push(entryArr[i][0]);
    }
    return resArr;
};

其实也可以使用大端堆，创建长度为n的大端堆，排序时只排出k个，就得到了前k大的数。

方法二：快速排序

快速排序每一轮都能确定一个元素的最终位置，

假如对数组arr[0,n-1]进行从大到小排序，一个数据pivot的最终位置为p，那么arr[0,p-1]的元素都不小于arr[p]，arr[p+1,n-1]的元素都不大于arr[p]。

判断k和p的大小：

如果k==p，那arr[0,p-1]就是前k大的元素。

如果k<p，那么再对arr[0,p-1]进行排序，找到k。

如果k>p，再对arr[p+1,n-2]进行排序，找到k。

这道题的思路和“第K大的元素”是类似的：

第K大的元素也可以使用快速排序（和本题思路一致），和堆排序（使用大端堆，大端堆排序的第k个元素就是第k大的元素。）