LeetCode 347. Top K Frequent Elements

LeetCode 347. Top K Frequent Elements 原题链接中等

作者：

yxc , 2018-06-28 22:45:17 , 所有人可见 , 阅读 2889

3

3

题目描述

给定一个非空整数数组，请返回出现次数最多的 $k$ 个数。

注意：

你可以假定 $k$ 一定是合法的，即 $1 \le k \le$ 数组中不同元素的个数，且排名在第 $k$ 位和排名在第 $k+1$ 位的数，出现次数不同；
你的算法一定要比 $O(nlogn)$ 快；

样例

给定 [1,1,1,2,2,3] 并且 k = 2,
返回 [1,2].

算法

(哈希表，计数排序) $O(n)$

首先用哈希表统计出所有数出现的次数。
由于所有数出现的次数都在 $1$ 到 $n$ 之间，所以我们可以用计数排序的思想，统计出次数最多的前 $k$ 个元素的下界。然后将所有出现次数大于等于下界的数输出。

时间复杂度分析：用哈希表统计每个数出现次数的计算量是 $O(n)$，计数排序的计算量是 $O(n)$，最终用下界过滤结果的计算量也是 $O(n)$，所以总时间复杂度是 $O(n)$。

C++ 代码

class Solution {
public:
    vector<int> topKFrequent(vector<int>& nums, int k) {
        unordered_map<int,int> hash;
        vector<int> res;
        for (int x : nums) hash[x] ++;
        int n = nums.size();
        vector<int>s(n + 1, 0);
        for (auto &p : hash) s[p.second] ++ ;
        int i = n, t = 0;
        while (t < k) t += s[i -- ];
        for (auto &p : hash)
            if (p.second > i)
                res.push_back(p.first);
        return res;
    }
};

9 评论

xju_wzp 2个月前

class Solution {
public:
    static bool comp(const pair<int,int> &a, const pair<int,int> &b) {
            return a.second > b.second;
        }
    vector<int> topKFrequent(vector<int>& nums, int k) {
        unordered_map<int,int> umap;
        for (auto c : nums) umap[c]++;
        vector<pair<int,int>> b;
        for (auto x : umap) b.push_back(x);
        sort(b.begin(),b.end(),comp);
        vector<int> res;
        for (int i = 0; i < k; i++) res.push_back(b[i].first);
        return res;
    }
};