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, 陣列中不同元素的數量]
• 題目保證答案是唯一的，也就是說前 k 個頻率最高的元素的出現次數不會相同

解題思路

解法一：最大堆積（Max Heap）

1. 統計頻率：使用一個雜湊表（Hash Map）來統計陣列中每個元素出現的次數。
2. 建立最大堆積：將每個元素及其頻率放入一個最大堆積中，堆積按照頻率從高到低排序。
3. 收集結果：從堆積中取出前 k 個元素，即為所需結果。

解題說明

1. 計算頻率：首先，我們用一個雜湊表 counter 來計算每個元素在陣列中出現的次數。
2. 使用最大堆積：接下來，使用一個優先佇列（Priority Queue）作為最大堆積，將每個元素及其頻率放入其中。優先佇列的比較依據是元素的出現次數。
3. 收集結果：最後，從優先佇列中取出前 k 個元素，放入結果陣列中。

複雜度分析

• 時間複雜度：O(n log n)
  1. 計算頻率：遍歷陣列一次，時間複雜度為 O(n)。
  2. 建立堆積：將所有元素插入堆積中，時間複雜度為 O(n log n)。
  3. 收集結果：從堆積中取出 k 個元素，時間複雜度為 O(k log n)。
• 空間複雜度：O(n)
  1. 雜湊表：儲存每個元素的出現次數，最多有 n 個不同的元素，空間複雜度為 O(n)。
  2. 堆積：最多儲存 n 個元素，空間複雜度為 O(n)。

程式碼

C++ 實作

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;
    }
};

Java 實作

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;
    }
}

解法二：桶排序（Bucket Sort）

1. 統計頻率：使用一個雜湊表來統計陣列中每個元素出現的次數。
2. 建立桶：創建一個桶陣列 bucket，索引代表頻率，值為具有該頻率的元素列表。
3. 收集結果：從高頻到低頻遍歷桶，收集元素直到達到 k 個。

解題說明

1. 計算頻率：使用雜湊表 count 記錄每個元素的出現次數。
2. 建立桶：創建一個大小為 n + 1 的桶陣列，因為元素的最大頻率不會超過陣列的長度 n。桶的索引代表頻率，值為具有該頻率的元素列表。
3. 收集結果：從索引最大的桶（最高頻率）開始，依次往下遍歷，收集元素直到收集到 k 個。

複雜度分析

• 時間複雜度：O(n)
  1. 計算頻率：遍歷陣列一次，時間複雜度為 O(n)。
  2. 建立桶：遍歷雜湊表一次，時間複雜度為 O(n)。
  3. 收集結果：最壞情況下，需要遍歷所有桶，時間複雜度為 O(n)。
• 空間複雜度：O(n)
  1. 雜湊表：儲存元素的頻率，空間複雜度為 O(n)。
  2. 桶陣列：大小為 n + 1，空間複雜度為 O(n)。

程式碼

C++ 實作

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;
    }
};

Java 實作

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;
    }
}