LeetCode347 前 K 个高频元素

发表于 | 分类于 |
字数统计: 474 | 阅读时长 ≈ 2

链接： https://leetcode.cn/problems/top-k-frequent-elements/

题意

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

解法

做法类似于top K
用一个哈希表统计一下每个数字出现的次数
然后可以通过快排或者优先队列的方式处理得到结果
学习了一下top K求最大的partition写法
还有一个有关优先队列的使用技巧：求最大的用小顶堆，求最小用大顶堆

代码

快速排序写法

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
35
36
37
38
39
40
41
42
43
44
45
46
#define pii pair<int, int>
class Solution {
public:
    int partition(vector<pii>& e, int l, int r) {
        swap(e[l], e[r]);
        int large = l;
        for (int i = l; i < r; i++) {
            if (e[i].second > e[r].second) {
                swap(e[i], e[large]);
                large++;
            }
        }
        swap(e[large], e[r]);
        return large;
    }
    void q_sort(vector<pii>& e, int l, int r, int k) {
        if (k == 0) return;
        int index = partition(e, l, r);
        while(index != k - 1) {
            if (index > k - 1) {
                r = index - 1;
            }
            else {
                l = index + 1;
            }
            index = partition(e, l, r);
        }
    }
    vector<int> topKFrequent(vector<int>& nums, int k) {
        unordered_map<int, int> mp;
        vector<int> ret;
        vector<pii> e;
        for (int i: nums) {
            mp[i]++;
        }
        for (auto idx: mp) {
            e.push_back(idx);
        }
        q_sort(e, 0, e.size() - 1, k);
        for (int i = 0; i < k; i++) {
            ret.push_back(e[i].first);
        }
        return ret;

    }
};

优先队列

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
class Solution {
public:
    vector<int> topKFrequent(vector<int>& nums, int k) {
        unordered_map<int, int> mp;
        priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
        vector<int> ret;
        for (int i: nums) {
            mp[i]++;
        }
        for (auto idx: mp) {
            if (pq.size() < k) {
                pq.push({idx.second, idx.first});
            }
            else {
                if (pq.top().first < idx.second) {
                    pq.pop();
                    pq.push({idx.second, idx.first});
                }
            }
        }
        while(pq.size()) {
            ret.push_back(pq.top().second);
            pq.pop();
        }
        return ret;

    }
};