347. Top K Frequent Elements

  • Hardness: \(\color{orange}\textsf{Medium}\)
  • Ralated Topics: Array、Hash Table、Divide and Conquer、Sorting、Heap (Priority Queue)、Bucket Sort、Counting、Quickselect

一、題目

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.

二、分析

  • 先以 HashMap 統計每個數字出現的頻率後，再以出現的頻率做排序。Bucket sort 或是 max heap。
  • priority_queue 的宣告方式。
    1. greater<> 與 less<>
    priority_queue<int, vector<int>, greater<int>> pq;  // descending order (min heap)
priority_queue<int, vector<int>, less<int>> pq;     // ascending order (max heap)
    1. custom comparactor
    auto comp = [](const auto& a, const auto& b) { return condition; } ;
priority_queue<element, container, decltype(comp)> pq(iterator::start, iterator::end, comp);
    1. default: max heap
    priority_queue<element> pq;   // 預設為 max heap

三、解題

1. Priority Queue

  • Time complexity: \(O(n\log k)\)
  • Space complexity: \(O(n)\)
vector<int> topKFrequent(vector<int>& nums, int k) {
    unordered_map<int,int> freq;
    for (const int& num : nums)     // 統計每個數字出現的次數
        freq[num]++;
    priority_queue<pair<int,int>> pq;
    for (const auto& x : freq)      // 用 max_heap 裝 {頻率, 數字}
        pq.push(make_pair(x.second, x.first));
    vector<int> res;
    while (k--) {       // 取出現頻率前 k 高的
        res.push_back(pq.top().second);
        pq.pop();
    }
    return res;
}

2. Bucket Sort

  • Time complexity: \(O(n)\)
  • Space complexity: \(O(1)\)
vector<int> topKFrequent(vector<int>& nums, int k) {
    unordered_map<int,int> freq;
    for (const int& num : nums)     // 統計每個數字出現的次數
        freq[num]++;
    vector<vector<int>> bucket;
    for (const auto f : freq) {
        while (bucket.size() <= f.second) {     // 將數字，依不同頻率次數放到相對應的 vector 中
            bucket.push_back({});
        }
        bucket[f.second].push_back(f.first);
    }
    vector<int> res;
    for (int i = bucket.size()-1; i >= 0; i--) {
        for (int j = 0; j < bucket[i].size() && k; j++, k--) {      // 拿頻率前 k 多的元素
            res.push_back(bucket[i][j]);
        }
    }
    return res;
}

回目錄 Catalog