[LeetCode刷題筆記] 347 - Top K Frequent Elements

題目描述：

Given a non-empty array of integers, return the *k* most frequent elements.

Example 1:

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

Example 2:

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

Note:

• You may assume k is always valid, 1 ≤ k ≤ number of unique elements.
• Your algorithm’s time complexity must be better than O(n log n), where n is the array’s size.
• It’s guaranteed that the answer is unique, in other words the set of the top k frequent elements is unique.
• You can return the answer in any order.

一刷題解（Dictionary）：

這題需要我們找出一數組裡出現次數最多的K個元素，因此，我們需要一個容器記錄「元素本身」和「元素出現頻次」兩個信息，那就非Dictionary莫屬了。首先遍歷數組，把所有元素本身為鍵，出現頻次為值記錄的字典裡，然後再讓字典根據值進行降序處理，那麼現在字典裡第一個元素肯定就是數組中出現頻次最多的元素。因此，我們再遍歷字典k次，依次把元素加到結果數組中即可。

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

        //Dictionary for save freq of nums[i]
        for (int i = 0; i < nums.Length; i++)
        {
            if (!freqDict.ContainsKey(nums[i]))
            {
                freqDict.Add(nums[i], 0);
            }
            freqDict[nums[i]]++;
        }

        //Sort Dictionary By Value(Descending)
        var sortedFreqDict = freqDict.OrderByDescending(x => x.Value);


        //Result array
        int[] res = new int[k];
        int counter = 0;
        //Loop the sortedDictionary
        foreach (var item in sortedFreqDict)
        {
            if(counter == k) { break; }
            res[counter] = item.Key;
            counter++;
        }

        return res;
    }
}