347. Top K Frequent Elements

題意

題目連結：Top K Frequent Elements

給定一個非空的整數陣列，回傳其中出現頻率最高的k個元素

題目理解

這道題目要求找出陣列中出現頻率最高的k個元素。可以簡單理解為：我們需要對陣列中每個元素的出現次數進行統計，然後根據這些次數找出出現次數最多的前k個元素

限制

• 1 <= nums.length <= 10^5
• -10^4 <= nums[i] <= 10^4
• k 的範圍是 [1, the number of unique elements in the array]
• 題目保證答案是唯一的，也就是說前k個頻率最高的元素的出現次數不會相同

解題思路

Solution 1：Max Heap

1. 統計頻率：使用一個 hash table 來統計數組中每個元素出現的次數
2. 使用優先隊列：將每個元素及其頻率放入一個max heap中，頂端元素即為當前頻率最高的元素
3. 收集結果：從heap中彈出k個元素即為所需結果

解題說明

1. 計算頻率：首先，我們用一個哈希表 counter 來計算每個元素在數組中出現的次數
2. 使用優先隊列：接下來，我們使用一個優先隊列 pq 來儲存每個元素及其出現次數，優先隊列的元素是{頻率, 元素} pair
3. 收集結果：最後，我們從優先隊列中彈出前k個元素，即為所需結果

複雜度分析

• Time Complexity: O(n log n)
  1. 計算頻率：需要遍歷陣列一次，時間複雜度為O(n)。
  2. 使用優先隊列：將每個元素放入priority queue中，時間複雜度為O(n log n)。
  3. 收集結果：從priority queue中彈出前k個元素，時間複雜度為O(k log n)
• Space Complexity: O(n)
  1. hash table：需要額外的空間來存儲每個元素的出現次數，空間複雜度為O(n)
  2. priority queue：需要額外的空間來存儲max heap中的元素，空間複雜度為O(n)

class Solution {
public:
    vector<int> topKFrequent(vector<int>& nums, int k) {
        const int n = nums.size();
        unordered_map<int, int> counter;
        priority_queue<pair<int, int>> pq;

        for (const int num : nums) {
            counter[num] += 1;
        }

        for (const auto [num, count] : counter) {
            pq.push({ count, num });
        }

        vector<int> ans;
        while (!pq.empty() && k--) {
            ans.push_back(pq.top().second);
            pq.pop();
        }

        return ans;
    }
};

class Solution {
    public int[] topKFrequent(int[] nums, int k) {
        HashMap<Integer, Integer> counter = new HashMap<>();
        for (int num : nums) {
            counter.put(num, counter.getOrDefault(num, 0) + 1);
        }

        PriorityQueue<Map.Entry<Integer, Integer>> maxHeap =
            new PriorityQueue<>((a, b) -> (b.getValue() - a.getValue()));

        for (Map.Entry<Integer, Integer> entry : counter.entrySet()) {
            maxHeap.add(entry);
        }

        int[] ans = new int[k];
        for (int i = 0; i < k; i += 1) {
            ans[i] = maxHeap.poll().getKey();
        }
        return ans;
    }
}

Solution 2: Bucket sort

1. 統計頻率：使用一個hash table來統計數組中每個元素出現的次數
2. 桶排序：將具有相同頻率的元素放入同一個桶中。桶的索引對應於元素的出現頻率
3. 收集結果：從頻率最高的桶開始，依次收集桶中的元素，直到收集到k個元素為止

解題說明

1. 計算頻率：首先，我們用一個哈希表 count 來計算每個元素在數組中出現的次數
2. Bucket sort: 我們使用一個 bucket，這個桶的大小是 n + 1，其中 n 是陣列的長度。桶的索引代表元素的出現頻率
3. 收集結果：最後，我們從最高頻率的桶開始，依次收集桶中的元素，直到收集到k個元素為止

複雜度分析

• Time Complexity: O(n)
  1. 計算頻率：需要遍歷陣列一次，時間複雜度為O(n)
  2. bucket sort：需要遍歷hash table一次，將元素放入對應的桶中，時間複雜度為O(n)
  3. 收集結果：需要遍歷桶中的元素，最壞情況下時間複雜度為O(n)
• Space Complexity: O(n)
  1. hash table：需要額外的空間來儲存每個元素的出現次數，空間複雜度為O(n)
  2. bucket：需要額外的空間來儲存每個頻率對應的元素列表，最壞情況下空間複雜度為O(n)

class Solution {
public:
    vector<int> topKFrequent(vector<int>& nums, int k) {
        const int n = nums.size();
        unordered_map<int, int> count;
        vector<vector<int>> bucket(n + 1, vector<int>());
        for (const int num : nums) {
            count[num] += 1;
        }
        for (auto [num, freq] : count) {
            bucket[freq].push_back(num);
        }

        vector<int> ans;
        for (int i = n; i > 0; i -= 1) {
            for (const int num : bucket[i]) {
                if (!k) {
                    return ans;
                }

                ans.push_back(num);
                k -= 1;
            }
        }

        return ans;
    }
};

class Solution {
    public int[] topKFrequent(int[] nums, int k) {
        HashMap<Integer, Integer> counter = new HashMap<>();

        for (int num : nums) {
            counter.put(num, counter.getOrDefault(num, 0) + 1);
        }

        List<Integer>[] bucket = new List[nums.length + 1];
        for (int num : counter.keySet()) {
            int freq = counter.get(num);
            if (bucket[freq] == null) {
                bucket[freq] = new LinkedList<>();
            }
            bucket[freq].add(num);
        }

        int[] ans = new int[k];
        for (int i = bucket.length - 1, p = 0; i > 0 && k > 0; i -= 1) {
            if (bucket[i] != null) {
                List<Integer> list = bucket[i];
                for (int num : list) {
                    if (k == 0) {
                        return ans;
                    }

                    ans[p++] = num;
                    k -= 1;
                }
            }
        }
        return ans;
    }
}