[Leetcode] 347. Top K Frequent Elements

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)
  

  複製
  2. custom comparactor

  auto comp = [](const auto& a, const auto& b) { return condition; } ;
  priority_queue<element, container, decltype(comp)> pq(iterator::start, iterator::end, comp);
  

  複製
  3. 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