LeetCode 347. Top K Frequent Elements-白红宇

LeetCode 347. Top K Frequent Elements

阅读量：6278 次

发布时间：2019-06-22

本文共 6368 字，大约阅读时间需要 21 分钟。

https://leetcode.com/problems/top-k-frequent-elements/

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.

频率排序问题，先HASH到MAP里，然后按照频率可以用桶排序，也可以用优先序列。

STL里vector, map, priority_queue和pair都重新学习了一遍，非常方便。

还学习了不少C++11的东西，比如Lambda 表达式, auto，unordered_map，Range-based for Statement。可惜Dev-C++ 4.9.9.2不支持，所以又写了C++98版本。

auto可以自动推断变量类型，如果不修改值的话，可以用const auto&。特别是对iterator很方便。

unordered_map性能比map更好。

Range-based for Statement更简洁，不需要写长串语句。可以对数组和STL sequence whose range is defined by a begin() and end()使用。Note that the keyword is preferred in the for-range-declaration portion of the statement.

C++11还可以像数组一样初始化vector，赋值一串数字。

1 #include 
      
        2 #include 
       
         3 #include 
        
          4 #include 
          5 #include 
          
            6 //#include 
           
             7 using namespace std; 8 9 class Solution 10 {11 public:12 vector
            
              topKFrequent(vector
             
              & nums, int k) 13 {14 // unordered_map
              
                frequencyMap;15 map
               
                 frequencyMap;16 vector
                
                 ::const_iterator vecCIt;17 18 // for (const auto &num : nums) 19 // frequencyMap[num] ++;20 21 for (vecCIt = nums.begin(); vecCIt != nums.end(); vecCIt ++)22 frequencyMap[*vecCIt] ++;23 24 vector
                 
                   res; 25 // pair
                  
                    : first is number, second is frequency26 // space is required between > and >27 priority_queue< pair
                   
                     > pq;28 map
                    
                     ::const_iterator mapCIt;29 30 /* 31 for (const auto &it : frequencyMap)32 {33 pq.push( make_pair(it.second, it.first) );34 35 if (pq.size() > (frequencyMap.size() - k))36 {37 res.push_back(pq.top().second);38 pq.pop();39 } 40 }41 */42 43 for (mapCIt = frequencyMap.begin(); mapCIt != frequencyMap.end(); mapCIt ++)44 {45 pq.push( make_pair(mapCIt->second, mapCIt->first) );46 47 if ( pq.size() > (frequencyMap.size() - k) )48 {49 res.push_back(pq.top().second);50 pq.pop();51 }52 }53 54 return res;55 }56 };57 58 int main ()59 {60 Solution testSolution;61 int arrRes[] = { 1, 1, 1, 2, 2, 3};62 // vector
                     
                       result{ {1, 1, 1, 2, 2, 3} };63 vector
                      
                        result(arrRes, arrRes + 6);64 vector
                       
                        ::const_iterator vecCIt;65 66 result = testSolution.topKFrequent(result, 2);67 68 for (vecCIt = result.begin(); vecCIt != result.end(); vecCIt ++)69 cout << *vecCIt << endl;70 71 getchar();72 73 return 0;74 }

Priority queue

1 #include 
      
        2 #include 
       
         3 #include 
        
          4 #include 
          5 #include 
          
            6 //#include 
           
             7 using namespace std; 8 9 class Solution 10 {11 public:12 vector
            
              topKFrequent(vector
             
              & nums, int k) 13 {14 // unordered_map
              
                frequencyMap;15 map
               
                 frequencyMap;16 map
                
                 ::const_iterator mapCIt;17 vector
                 
                  ::const_iterator vecCIt;18 19 // for (const auto &num : nums) 20 // frequencyMap[num] ++;21 22 for (vecCIt = nums.begin(); vecCIt != nums.end(); vecCIt ++)23 frequencyMap[*vecCIt] ++;24 25 // 2-d vector based on frequency including frequecy 026 vector< vector
                  
                    > buckets(nums.size() + 1);27 vector
                   
                    ::const_iterator vecVCIt;28 29 // Pay attention to .first/.second rather than ->first/->second30 // for (auto mapCIt : frequencyMap)31 // buckets[mapCIt.second].push_back(mapCIt.first); 32 33 // Numbers with the same frequency will be pushed back to the same buckets[i]34 for (mapCIt = frequencyMap.begin(); mapCIt != frequencyMap.end(); mapCIt ++)35 buckets[mapCIt->second].push_back(mapCIt->first); 36 37 vector
                    
                      res;38 /* 39 for (int i = buckets.size() - 1; i >= 0 && res.size() < k; i --)40 {41 for (int num : buckets[i])42 {43 res.push_back(num);44 if (res.size() == k)45 break;46 } 47 }48 */49 50 // Find k numbers from the end of buckets to the front51 for (int i = buckets.size() - 1; i >= 0 && res.size() < k; i --)52 {53 // Find the numbers in the same buckets[frequency]54 for (vecVCIt = buckets[i].begin(); vecVCIt != buckets[i].end(); vecVCIt ++)55 {56 res.push_back(*vecVCIt);57 if (res.size() == k)58 break;59 } 60 }61 62 return res;63 }64 };65 66 int main ()67 {68 Solution testSolution;69 int arrRes[] = { 1, 1, 1, 2, 2, 3};70 // vector
                     
                       result{ {1, 1, 1, 2, 2, 3} };71 vector
                      
                        result(arrRes, arrRes + 6);72 vector
                       
                        ::const_iterator vecCIt;73 74 result = testSolution.topKFrequent(result, 2);75 76 for (vecCIt = result.begin(); vecCIt != result.end(); vecCIt ++)77 cout << *vecCIt << endl;78 79 getchar();80 81 return 0;82 }

Bucket sort

Lambda

http://baike.baidu.com/link?url=ZK0qILx8cb_8HUX13JvVUYdnlJBOvAPJdWF83wD-tDgQQwIQYAVzkhytf_3f7oidHLPeTyXSswQUWVW51W42Ri4Pp8vnnkFHBCloSSTyS9xIT2pAV8a2zknUKK1UkjhDMzr4O7-qrD6J-lkJxET4u_#4

C++ 中的 Lambda 表达式

https://msdn.microsoft.com/zh-cn/library/dd293608.aspx

C++ STL编程轻松入门

http://tech.163.com/05/0613/10/1M4EA0US00091589.html

STL （模板库）

http://baike.baidu.com/link?url=IZpCuRuYLNA31OpA8x1h3urVpkYzp2K8oCssu_nkwqOqFdrMhL9drd9FnAg-Ru_D2690xbC0e3Q-W9QxF47gsUXTXdMmS5Vl_jNeFK0GXOa

Map（STL关联容器）_百度百科

http://baike.baidu.com/subview/95826/8050590.htm#viewPageContent

map 类

https://msdn.microsoft.com/zh-CN/library/s44w4h2s.aspx

vector（Java与C++语言中的对象）_百度百科

http://baike.baidu.com/item/vector/3330482