LeetCode 347. 前 K 个高频元素（hash 以及 vector 下标的巧妙使用） and 692. 前K个高频单词_leecode 的vector下标

题目描述
给你一个整数数组 nums 和一个整数 k ，请你返回其中出现频率前 k 高的元素。你可以按 任意顺序 返回答案。

示例 1:
输入: nums = [1,1,1,2,2,3], k = 2
输出: [1,2]
示例 2:
输入: nums = [1], k = 1
输出: [1]

题目要求是出现频率前k个，按照样例1来讲，1出现的次数是3次，2出现的次数是2次，3出现的次数是1次，要求解出现频率在前2的，那么就是数字1和数字2。用哈希表统计出所有数字出现的次数（hash表是按照key关键词排序的链接）。可以采用计数排序的思想，统计出现次数是1的有几个数字，频率为2的有几个数字，频率为3的有几个数字……，这些数字存储到了vector数组中，将下标看成是出现的频率，值看成是出现该频率值的数的个数，由于是前k个频率最高的数字，那么就需要从计数排序中倒着去计算出现频率最高的k个频次，找到下标 i ，也就是找到频次 i 意味着在频次 i 之后的数字都是要求解的前k个高频元素。最后hash表中找到频次大于 i 的数字即可。

class Solution {
public:
    vector<int> topKFrequent(vector<int>& nums, int k) {
        unordered_map<int,int> cnt;
        for(auto x:nums) cnt[x]++;
        int n=nums.size();
        vector<int> s(n+1);
        for(auto [x,c]:cnt) s[c]++;
        int i=n,t=0;
        while(t<k) t+=s[i--];
        vector<int> res;
        for(auto [x,c]:cnt)
        {
            if(c>i) res.push_back(x);
        }
        return res;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

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 ≤ 集合元素数。
输入的单词均由小写字母组成。

使用C++中自带的make_heap()建堆，先统计每个单词出现的次数，然后根据次数排序，当次数不相等时次数大的在后面，当次数相等时，字典序小的在后面，此时建堆相当于是大根堆，题目要求是前k个，将元素不断从大根堆中取出，取出k个元素为止。

class Solution {
public:
    typedef pair<int,string> PIS;
    vector<string> topKFrequent(vector<string>& words, int k) {
        unordered_map<string,int> cnt;
        for(auto x:words) cnt[x]++;
        vector<PIS> ws;
        for(auto [k,v]:cnt) ws.push_back({v,k});
        auto cmp=[](PIS a,PIS b)
        {
            if(a.first!=b.first) return a.first<b.first;
            return a.second > b.second;
        };
        make_heap(ws.begin(),ws.end(),cmp);
        vector<string> res;
        while(k--)
        {
            res.push_back(ws[0].second);
            pop_heap(ws.begin(),ws.end(),cmp);
            ws.pop_back();
        }
        return res;
    }  
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24