当前位置：网站首页>LeetCode-692. Top K Frequent Words

LeetCode-692. Top K Frequent Words

2022-08-10 15:35:00 【51CTO】


Given a non-empty list of words, return the k most frequent elements.

Your answer should be sorted by frequency from highest to lowest. If two words have the same frequency, then the word with the lower alphabetical order comes first.

Example 1:

      
      

       
       Input: ["i", "love", "leetcode", "i", "love", "coding"], k = 2
       
       
Output: ["i", "love"]
       
       
Explanation: "i" and "love" are the two most frequent words.
       
       
    Note that "i" comes before "love" due to a lower alphabetical order.
      
      

      
      
    
       
       
  • 1.
    • 
       
       
  • 2.
    • 
       
       
  • 3.
    • 
       
       
  • 4.
    •

 

Example 2:

      
      

       
       Input: ["the", "day", "is", "sunny", "the", "the", "the", "sunny", "is", "is"], k = 4
       
       
Output: ["the", "is", "sunny", "day"]
       
       
Explanation: "the", "is", "sunny" and "day" are the four most frequent words,
       
       
    with the number of occurrence being 4, 3, 2 and 1 respectively.
      
      

      
      
    
       
       
  • 1.
    • 
       
       
  • 2.
    • 
       
       
  • 3.
    • 
       
       
  • 4.
    •

 

Note:

  1. You may assumekis always valid, 1 ≤k≤ number of unique elements.
  2. Input words contain only lowercase letters.

 

Follow up:

  1. Try to solve it inO(nlogk) time andO(n) extra space.

题解：

      
      

       
       class 
       
       Solution {
       
       
  
       
       static 
       
       bool 
       
       cmp(
       
       pair
       
       <
       
       string, 
       
       int
       
       > 
       
       a, 
       
       pair
       
       <
       
       string, 
       
       int
       
       > 
       
       b) {
       
       
    
       
       if (
       
       a.
       
       second 
       
       == 
       
       b.
       
       second) {
       
       
      
       
       return 
       
       a.
       
       first 
       
       < 
       
       b.
       
       first;
       
       
    }
       
       
    
       
       return 
       
       a.
       
       second 
       
       > 
       
       b.
       
       second;
       
       
  }
       
       
  
       
       public:
       
       
    
       
       vector
       
       <
       
       string
       
       > 
       
       topKFrequent(
       
       vector
       
       <
       
       string
       
       >& 
       
       words, 
       
       int 
       
       k) {
       
       
      
       
       int 
       
       n 
       
       = 
       
       words.
       
       size();
       
       
      
       
       map
       
       <
       
       string, 
       
       int
       
       > 
       
       m;
       
       
      
       
       for (
       
       int 
       
       i 
       
       = 
       
       0; 
       
       i 
       
       < 
       
       n; 
       
       i
       
       ++) {
       
       
        
       
       if (
       
       m.
       
       find(
       
       words[
       
       i]) 
       
       == 
       
       m.
       
       end()) {
       
       
          
       
       m.
       
       insert(
       
       pair
       
       <
       
       string, 
       
       int
       
       >(
       
       words[
       
       i], 
       
       1));
       
       
        }
       
       
        
       
       else {
       
       
          
       
       m[
       
       words[
       
       i]]
       
       ++;
       
       
        }
       
       
      }
       
       
      
       
       vector
       
       <
       
       pair
       
       <
       
       string, 
       
       int
       
       >> 
       
       vm(
       
       m.
       
       begin(), 
       
       m.
       
       end());
       
       
      
       
       vector
       
       <
       
       string
       
       > 
       
       ans;
       
       
      
       
       sort(
       
       vm.
       
       begin(), 
       
       vm.
       
       end(), 
       
       cmp);
       
       
      
       
       for (
       
       int 
       
       i 
       
       = 
       
       0; 
       
       i 
       
       < 
       
       k; 
       
       i
       
       ++) {
       
       
        
       
       ans.
       
       push_back(
       
       vm[
       
       i].
       
       first);
       
       
      }
       
       
      
       
       return 
       
       ans;
       
       
    }
       
       
};
      
      

      
      
    
       
       
  • 1.
    • 
       
       
  • 2.
    • 
       
       
  • 3.
    • 
       
       
  • 4.
    • 
       
       
  • 5.
    • 
       
       
  • 6.
    • 
       
       
  • 7.
    • 
       
       
  • 8.
    • 
       
       
  • 9.
    • 
       
       
  • 10.
    • 
       
       
  • 11.
    • 
       
       
  • 12.
    • 
       
       
  • 13.
    • 
       
       
  • 14.
    • 
       
       
  • 15.
    • 
       
       
  • 16.
    • 
       
       
  • 17.
    • 
       
       
  • 18.
    • 
       
       
  • 19.
    • 
       
       
  • 20.
    • 
       
       
  • 21.
    • 
       
       
  • 22.
    • 
       
       
  • 23.
    • 
       
       
  • 24.
    • 
       
       
  • 25.
    • 
       
       
  • 26.
    • 
       
       
  • 27.
    • 
       
       
  • 28.
    •

 

原网站

版权声明
本文为[51CTO]所创，转载请带上原文链接，感谢
https://blog.51cto.com/u_14150327/5564022

边栏推荐

猜你喜欢

随机推荐