跳至主要內容

347. Top K Frequent Elements

347. Top K Frequent Elementsopen in new window

🟠   🔖  数组 哈希表 分治 桶排序 计数 快速选择 排序 堆（优先队列）  🔗 LeetCodeopen in new window

题目

Given an integer array nums and an integer k, return the k most frequent elements. You may return the answer in any order.

Example 1:

Input: nums = [1,1,1,2,2,3], k = 2

Output: [1,2]

Example 2:

Input: nums = [1], k = 1

Output: [1]

Constraints:

  • 1 <= nums.length <= 10^5
  • -10^4 <= nums[i] <= 10^4
  • k is in the range [1, the number of unique elements in the array].
  • It is guaranteed that the answer is unique.

Follow up: Your algorithm's time complexity must be better than O(n log n), where n is the array's size.

题目大意

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

解题思路

可以使用哈希映射和小顶堆来实现：

  1. 使用哈希映射存储数组中每个元素的频率。
  2. 创建一个小顶堆（优先队列），用于跟踪出现频率最高的 k 个元素。
  3. 遍历哈希映射，将元素和其频率添加到小顶堆中，拿它与堆顶的元素对比。
    • 如果比堆顶元素大，就把堆顶元素删除，并且将这个元素插入到堆中；
    • 如果比堆顶元素小，则不做处理；
  4. 处理完所有元素后，小顶堆中将包含 k 个最高频率的元素。

这个算法的时间复杂度为 O(n log k)，其中 n 是数组的大小，k 是唯一元素的数量，相较于传统排序算法的 O(n log n) 更为高效。

代码

/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number[]}
 */
var topKFrequent = function (nums, k) {
  let map = new Map();
  for (let i of nums) {
    map.set(i, map.has(i) ? map.get(i) + 1 : 1);
  }
  let heap = [];

  const add = ([val, freq]) => {
    if (heap.length < k) {
      heap.push([val, freq]);
      heapifyUp(heap.length - 1);
    } else if (heap[0][1] < freq) {
      heap[0] = [val, freq];
      heapifyDown(0);
    }
  };
  const heapifyUp = (i) => {
    while (i > 0) {
      const parent = Math.floor((i - 1) / 2);
      if (heap[i][1] < heap[parent][1]) {
        [heap[parent], heap[i]] = [heap[i], heap[parent]];
        i = parent;
      } else {
        break;
      }
    }
  };
  const heapifyDown = (i) => {
    const left = 2 * i + 1;
    const right = 2 * i + 2;
    let min = i;
    if (left < heap.length && heap[left][1] < heap[min][1]) {
      min = left;
    }
    if (right < heap.length && heap[right][1] < heap[min][1]) {
      min = right;
    }
    if (min !== i) {
      [heap[i], heap[min]] = [heap[min], heap[i]];
      heapifyDown(min);
    }
  };

  for (item of map.entries()) {
    add(item);
  }
  return heap.map((i) => i[0]);
};

相关题目

相关题目
- [192. 统计词频](https://leetcode.com/problems/word-frequency)
- [215. 数组中的第 K 个最大元素](https://leetcode.com/problems/kth-largest-element-in-an-array)
- [451. 根据字符出现频率排序](https://leetcode.com/problems/sort-characters-by-frequency)
- [659. 分割数组为连续子序列](https://leetcode.com/problems/split-array-into-consecutive-subsequences)
- [692. 前 K 个高频单词](https://leetcode.com/problems/top-k-frequent-words)
- [973. 最接近原点的 K 个点](https://leetcode.com/problems/k-closest-points-to-origin)
- [🔒 Sort Features by Popularity](https://leetcode.com/problems/sort-features-by-popularity)
- [2284. 最多单词数的发件人](https://leetcode.com/problems/sender-with-largest-word-count)
- [2404. 出现最频繁的偶数元素](https://leetcode.com/problems/most-frequent-even-element)
Copyright © 2024 2xiao