【Day24】692.前K个高频单词

692. 前K个高频单词

给一非空的单词列表,返回前 k 个出现次数最多的单词。

返回的答案应该按单词出现频率由高到低排序。如果不同的单词有相同出现频率,按字母顺序排序。

示例 1:

输入: ["i", "love", "leetcode", "i", "love", "coding"], k = 2
输出: ["i", "love"]
解析: "i" 和 "love" 为出现次数最多的两个单词,均为2次。
    注意,按字母顺序 "i" 在 "love" 之前。

示例 2:

输入: ["the", "day", "is", "sunny", "the", "the", "the", "sunny", "is", "is"], k = 4
输出: ["the", "is", "sunny", "day"]
解析: "the", "is", "sunny" 和 "day" 是出现次数最多的四个单词,
    出现次数依次为 4, 3, 2 和 1 次。

注意:

  • 假定 k 总为有效值, 1 ≤ k ≤ 集合元素数。
  • 输入的单词均由小写字母组成。

扩展练习:

尝试以 O(n log k) 时间复杂度和 O(n) 空间复杂度解决。

题解:

struct Cmp {
    bool operator()(const pair& p1, const pair& p2) {
        if(p1.second != p2.second) return p1.second > p2.second;
        else return p1.first < p2.first;
    }
};

class Solution {
public:
    vector topKFrequent(vector& words, int k) {
        unordered_map m;
        for(string& word : words) m[word]++;
        vector> sorted_list(m.begin(), m.end());
        sort(sorted_list.begin(), sorted_list.end(), Cmp());
        vector res;
        for(int i = 0; i < k; i++) res.push_back(sorted_list[i].first);
        return res;
    }
};

   转载规则


《【Day24】692.前K个高频单词》 Tyzhao 采用 知识共享署名 4.0 国际许可协议 进行许可。
 上一篇
【Day25】1035.不相交的线 【Day25】1035.不相交的线
1035. 不相交的线在两条独立的水平线上按给定的顺序写下 nums1 和 nums2 中的整数。 现在,可以绘制一些连接两个数字 nums1[i] 和 nums2[j] 的直线,这些直线需要同时满足满足: nums1[i] == num
2021-05-21
下一篇 
【Day23】1738.找出第 K 大的异或坐标值 【Day23】1738.找出第 K 大的异或坐标值
1738. 找出第 K 大的异或坐标值给你一个二维矩阵 matrix 和一个整数 k ,矩阵大小为 m x n 由非负整数组成。 矩阵中坐标 (a, b) 的 值 可由对所有满足 0 <= i <= a < m 且 0 &
2021-05-19
  目录