LeetCode

LeetCode-优先队列相关

STL中priority—queue的定义，需要给出元素类型，容器类型，比较函数。其中比较函数可以由lambda函数，或struct定义。最常使用的操作有push(), top(), pop()。

347 Top-K freqent elements

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
vector<int> topKFrequent(vector<int>& nums, int k){
	// 1) build a map:
	unordered_map<int, int>mp;
	for(auto item: nums){
		mp[item]++;
	}

	// 2) build a heap: make_pair<frequent, value>
	auto Comp = [](pair<int, int>& a, pair<int, int>& b) {
		return a.first < b.first;
	};
	priority_queue<pair<int, int>, vector<pair<int, int>>, decltype(Comp)> pq(Comp);
	for(auto itr=mp.begin(); itr!=mp.end(); itr++){
		pq.push(make_pair(itr->second, itr->first));
	}

	// 3) push top k of heap to 'res'
	vector<int> res;
	for(int i=0;i<k;i++){
		res.push_back(pq.top().second);
		pq.pop();
	}

	return res;
}

如测试用例：{1,1,1,1,2,2,2,2,2,2,3,3,3,3,3,4,4,4,5,6,7,8} 返回频数最大的前3个元素2,3,1。

692 Top-K freqent words

同上一个问题

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
29
30
31
32
33
34
vector<string> topKFrequent(vector<string>& words, int k) {
    // 1) build a map
    unordered_map<string, int> mp;
    for(auto item: words)
        mp[item]++;

    //2) build a Max heap
    // 2.1) use lambda func and pass lambda to 'pq'
    auto comp = [](pair<int, string>& a, pair<int, string>& b){
        return a.first<b.first || (a.first==b.first && a.second>b.second);
    };
    
    priority_queue<pair<int, string>, vector<pair<int, string>>, decltype(comp)> pq(comp);

    // 2.2) declare container && the element type
    // priority_queue<pair<int,string>, vector<pair<int, string>>, Comp> pq;

    for(auto itr=mp.begin(); itr!=mp.end(); itr++)
        pq.push(make_pair(itr->second, itr->first));

    // 3) push top k words to 'res'
    vector<string> res;
    for(int i=0;i<mp.size();i++){
        cout<<pq.top().second<<": "<<pq.top().first<<" ";
        res.push_back(pq.top().second);
        pq.pop();
    }
    cout<<endl;
    return res;
}
struct Comp{
    bool operator()(pair<int, string>& a, pair<int, string>& b)
        return a.first<b.first || (a.first==b.first && a.second>b.second);
}