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