21-05-29-前 K 个高频元素

题目地址

https://leetcode-cn.com/problems/top-k-frequent-elements

题目描述

给定一个非空的整数数组，返回其中出现频率前  k  高的元素。
示例 1:


输入: nums = [1,1,1,2,2,3], k = 2
输出: [1,2]


示例 2:


输入: nums = [1], k = 1
输出: [1]


提示：

- 你可以假设给定的  k  总是合理的，且 1 ≤ k ≤ 数组中不相同的元素的个数。
- 题目数据保证答案唯一，换句话说，数组中前 k 个高频元素的集合是唯一的。
- 你可以按任意顺序返回答案。

进阶：
- 你的算法的时间复杂度必须优于 O(n log n) , n 是数组的大小。

思路

• 比较清晰一股脑。
• 哈希表，存下来元素的出现次数。
• 按照出现次数排序，然后取出头k个。

代码

/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number[]}
 */
var topKFrequent = function(nums, k) {
  let length = nums.length;
  if (length <= 1) return nums;
  const map = new Map();
  for (let i = 0; i < length; i++) {
    const mapEl = map.get(nums[i]);
    if (mapEl !== void 0) {
      map.set(nums[i], mapEl + 1);
    } else {
      map.set(nums[i], 1);
    }
  }
  return Array.from(map.keys()).sort((a, b) => map.get(b) - map.get(a))
    .slice(0, k)
};

复杂度分析

• 时间复杂度：O(NlogN)，排序用了O(NlogN)
• 空间复杂度：O(N)，存取出现次数的map的开销

进阶思路

时间复杂度要优于O(NlogN)，需要使用堆。前K大这种关键词一般都要联想到用堆。

代码

复杂度分析