題目在問什麼

給一個整數陣列 nums，要你找出出現頻率最高的前 k 個元素。

重點不是只把頻率算出來而已，題目還額外要求：

  • 時間複雜度要優於 O(n log n)
  • 回傳順序不限
  • 題目保證答案唯一

例子

Input: nums = [1,1,1,2,2,3], k = 2
Output: [1,2]

解題思路

先用 Dictionary<int, int> 統計每個數字出現幾次。

如果接著把整張頻率表排序，時間複雜度會是 O(n log n)，不符合題目要求。所以這題更適合用 bucket sort 的想法：

  1. 先統計每個數字的頻率
  2. 建一個陣列 buckets，索引代表「出現次數」
  3. 把相同頻率的數字丟進對應 bucket
  4. 從高頻往低頻掃回來，收集前 k 個元素

因為一個元素最多只會出現 nums.Length 次，所以 bucket 陣列的大小開到 nums.Length + 1 就夠了。

為什麼這題不要直接排序

直接排序確實很好寫，但排序的是所有不同元素的頻率資料，成本至少是 O(m log m)，m 是不同元素的數量。

這題的關鍵在於：

  • 頻率的範圍其實是有限的
  • 頻率只會落在 1 ~ nums.Length

既然頻率範圍固定，就可以直接用 bucket 把元素分桶，省掉整體排序。

代碼

public class Solution
{
    public int[] TopKFrequent(int[] nums, int k)
    {
        Dictionary<int, int> freq = new Dictionary<int, int>();

        foreach (int num in nums)
        {
            if (!freq.ContainsKey(num))
            {
                freq.Add(num, 0);
            }

            freq[num]++;
        }

        List<int>[] buckets = new List<int>[nums.Length + 1];

        foreach (var pair in freq)
        {
            int count = pair.Value;

            if (buckets[count] == null)
            {
                buckets[count] = new List<int>();
            }

            buckets[count].Add(pair.Key);
        }

        List<int> result = new List<int>();

        for (int i = buckets.Length - 1; i >= 0 && result.Count < k; i--)
        {
            if (buckets[i] == null)
            {
                continue;
            }

            foreach (int num in buckets[i])
            {
                result.Add(num);

                if (result.Count == k)
                {
                    break;
                }
            }
        }

        return result.ToArray();
    }
}

複雜度

  • 時間複雜度：O(n)
  • 空間複雜度：O(n)

這題先記住的重點

  • 題目要求優於 O(n log n) 時，不要下意識先排序
  • 先看資料是不是有「值域有限」這種特性
  • 頻率統計題很常搭配 Dictionary 或 bucket sort