347. Top K Frequent Elements

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

Question

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

思路

做这一题的初衷是去学习桶排序的分治思想，所以一开始就用桶排序+hash map的方式去做。

桶排序的优点是可以把一组大的数据分成小的，在内存和多线程处理上就会有较大的优势。

var topKFrequent = function (nums, k) {
  let maxCount = 0;
  const map = {};
  // 统计每个数字出现次数
  nums.forEach((num) => {
    map[num] = (map[num] || 0) + 1;
    maxCount = Math.max(map[num], maxCount);
  });
  // 按出现次数为顺序，分桶
  const buckets = [];
  Object.keys(map).forEach((num) => {
    const count = map[num];
    if (!buckets[count]) buckets[count] = [];
    buckets[count].push(num);
  });
  const res = [];
  for (let i = maxCount; i >= 0; i--) {
    if (k < 1) break;
    if (!buckets[i]?.length) continue;
    for (let j = 0; j < buckets[i].length; j++) {
      const num = buckets[i][j];
      res.push(num);
      k--;
    }
  }
  return res;
};

End

桶排序的处理对于分治是一种很好的理解手段。