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.

 to see which companies asked this question

 

Solution:

1.使用hashtable获取每个元素出现的次数

2.使用小根堆heap排序（priority queue实现），获取前K个出现次数最多的元素pair

3.输出，注意是小根堆，要reverse一下

时间复杂度：O(N * logK)

1 class CompareDist 2 { 3 public: 4     bool operator()(pair
     
       n1, pair
      
        n2)  5     { 6         return n1.second > n2.second; 7     } 8 }; 9 10 class Solution {11 public:12     vector
       
         topKFrequent(vector
        
         & nums, int k) 13     {14         vector
         
           ret;15         unordered_map
          
            htable;16 17 for (int key : nums) // get each key appears times18 htable[key]++;19 20 priority_queue
           
            
             , vector
             
              
                >, CompareDist> sheap; // use min heap to get k biggest21 for (auto elem : htable)22 {23 if (sheap.size() < k)24 {25 sheap.push(elem);26 }27 else28 {29 pair
               
                 heap_min = sheap.top();30 if (elem.second > heap_min.second)31 {32 sheap.pop();33 sheap.push(elem);34 }35 }36 }37 38 while (!sheap.empty())39 {40 pair
                
                  heap_min = sheap.top();41 ret.push_back(heap_min.first);42 sheap.pop();43 }44 reverse(ret.begin(), ret.end());45 46 return ret;47 }48 };
                
               
              
             
            
           
          
         
        
       
      
     

 

或者直接使用make_heap操作，时间复杂度O(N + KlogN) = O(N)

1 vector
     
       topKFrequent(vector
      
       & nums, int k)  2     { 3         unordered_map
       
         htable; 4         for (auto &n : nums)  5             htable[n]++; 6  7         vector
        
         
          > heap; 8         for (auto &i : htable)  9             heap.push_back({i.second, i.first});10 11         vector
          
            result;12 make_heap(heap.begin(), heap.end());13 while (k--) 14 {15 result.push_back(heap.front().second);16 pop_heap(heap.begin(), heap.end());17 heap.pop_back();18 }19 return result;20 }