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

For example,

Given [1,1,1,2,2,3] and k = 2, return [1,2].

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.

1 public class Solution { 2     public IList
     
       TopKFrequent(int[] nums, int k) { 3         var dict = new Dictionary
      
       (); 4          5         foreach (var n in nums) 6         { 7             if (!dict.ContainsKey(n)) 8             { 9                 dict[n] = 0;10             }11             12             dict[n]++;13         }14         15         var freq = new List
       
        [nums.Length + 1];16         17         foreach (var kv in dict)18         {19             if (freq[kv.Value] == null)20             {21                 freq[kv.Value] = new List
        
         ();22             }23             24             freq[kv.Value].Add(kv.Key);25         }26         27         var result = new List
         
          ();28         for (int i = nums.Length; i >= 0; i--)29         {30             if (freq[i] != null)31             {32                 foreach (var v in freq[i])33                 {34                     result.Add(v);35                     if (result.Count >= k) return result;36                 }37             }38         }39         40         return result;41     }42 }