347. Top K Frequent Elements

Leetcode link

解题思路——最小堆

• TC:
• SC:

我们可以维护一个 map，来保存数组元素与出现频率，然后再维护一个优先队列构造的最小堆，里面保存了元素从小到大的出现频率

最后再一次遍历把前 k 小的元素丢进数组里就好了

C++

class Solution {
 public:
  vector<int> topKFrequent(vector<int>& nums, int k) {
    unordered_map<int, int> map;
    for (int n : nums) {
      map[n]++;
    }

    priority_queue<int, vector<int>, greater<int>> pq;
    for (auto& m : map) {
      pq.push(m.second);
      // 如果超出 k 个元素，就不保存了，这样能保证优先队列的头一定是第 k 大的
      if (pq.size() > k) {
        pq.pop();
      }
    }

    vector<int> res;
    for (auto& m : map) {
      if (m.second >= pq.top()) {
        res.push_back(m.first);
      }
    }
    return res;
  }
};

Javascript

/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number[]}
 */
var topKFrequent = function(nums, k) {
    let map = {}
    for(let n of nums){
        map[n]?map[n]++ : map[n] = 1;
    }

    let arr = [];
    for(let key in map) {
        arr.push([Number(key), map[key]]);
    }
      // 偷懒一下直接用 sort
    arr.sort((a,b)=>b[1]-a[1]);

    let res = [];
    for(let i = 0;i<k;i++) {
        res.push(arr[i][0]);
    }
    return res;
};

解题思路——桶排序

• TC:
• SC:

与上面的最小堆一样，我们还是先用一个 map 来统计频率。但是这次不同的是，我们用一个数组，把频率作为下标，依次把元素填进数组里。这样一来只要由后往前遍历，就能依次得到前 k 大高频元素了

C++

class Solution {
 public:
  vector<int> topKFrequent(vector<int>& nums, int k) {
    unordered_map<int, int> map;
    for (int n : nums) {
      map[n]++;
    }

    vector<vector<int>> bucket(nums.size() + 1);
    for (auto& m : map) {
      bucket[m.second].push_back(m.first);
    }

    vector<int> res;
    for (int i = bucket.size() - 1; i >= 0; i--) {
      for (int j = 0; j < bucket[i].size(); j++) {
        res.push_back(bucket[i][j]);
        if (res.size() == k) {
          return res;
        }
      }
    }
    return res;
  }
};