前 K 个高频元素

题意

返回数组中频次前 k 高的元素。

思路

先用哈希表统计每个元素的频次，再按频次降序排序取前 k 个。C++ 直接排序；Python 用 Counter.most_common(k)。

代码

cpp

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#include <bits/stdc++.h>
using namespace std;

class Solution {
public:
    vector<int> topKFrequent(vector<int> &nums, int k) {
        unordered_map<int, int> cnt;
        for (int x : nums)
            cnt[x]++;
        vector<pair<int, int>> v(cnt.begin(), cnt.end());
        sort(v.begin(), v.end(), [](auto &a, auto &b) { return a.second > b.second; });
        vector<int> ans(k);
        for (int i = 0; i < k; i++)
            ans[i] = v[i].first;
        return ans;
    }
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, k;
    cin >> n >> k;
    vector<int> a(n);
    for (int &x : a)
        cin >> x;
    for (int x : Solution().topKFrequent(a, k))
        cout << x << ' ';
    return 0;
}

python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18#!/usr/bin/env python3
from typing import List
from collections import Counter


class Solution:
    def topKFrequent(self, nums: List[int], k: int) -> List[int]:
        return [x for x, _ in Counter(nums).most_common(k)]


def main():
    n, k = map(int, input().split())
    a = list(map(int, input().split()))
    print(*Solution().topKFrequent(a, k))


if __name__ == "__main__":
    main()

复杂度

时间复杂度： $O(n \log n)$ （排序），可用堆优化到 $O(n \log k)$ 。
空间复杂度： $O(n)$ ，频次表。

总结

频次统计 + 排序取前 k 是本题最直接的解法。堆优化时维护大小为 k 的最小堆，按频次弹出不够格的元素。

目录

题意

思路

代码

复杂度

总结