leetcode 347. Top K Frequent Elements

1.题目

Given a non-empty array of integers, return the k most frequent elements.
一个非空数组，要求返回前K个最频繁出现的元素
For example,
Given [1,1,1,2,2,3] and k = 2, return [1,2].
K一定是有效的，要求时间复杂度小于O(nlogn)
Note:
You may assume k is always valid, 1 ≤ k ≤ number of unique elements.
Your algorithm’s time complexity must be better than O(n log n), where n is the array’s size.

2.分析

1)统计每个元素出现的次数
2)找出出现次数前K个元素
a. 牺牲空间换时间桶排序
b. 借助数据结构，例如最大堆或最小堆，维护一个大小为k的最小堆或者大小为n-k的最大堆

3.代码

小根堆-priority-queue
priority-queue默认是最大堆，第一个元素是队列中所有元素的最大值。
使用greater函数对象作为比较器可以得到最小堆。
这里需要维护一个大小为k的最小堆。

class Solution {
public:
    vector<int> topKFrequent(vector<int>& nums, int k) {
        vector<int> ans;
        unordered_map<int, int> hashMap;
        for (auto x : nums)
            ++hashMap[x];
        priority_queue<int, vector<int>, greater<int>> min_heap;
        for (auto p : hashMap) {
            min_heap.push(p.second);
            if (min_heap.size() > k)
                min_heap.pop();
        }
        //最终最小堆里保存的是前k的出现次数。第一个元素是出现第k多的次数。
        for (auto p : hashMap) {
            if (p.second >= min_heap.top())
                ans.push_back(p.first);
        }
        return ans;
    }
};

桶排序

class Solution {
public:
    vector<int> topKFrequent(vector<int>& nums, int k) {
        vector<int> ans;
        if (nums.size() < 1)
            return ans;
        unordered_map<int, int> hashMap;
        for (auto x : nums)
            ++hashMap[x];
        vector<vector<int>> bucket(nums.size() + 1);
        for (auto p : hashMap)
            bucket[p.second].push_back(p.first);
        reverse(bucket.begin(),bucket.end());
        for (auto p : bucket) {
            for (auto x : p) {
                ans.push_back(x);
                if (ans.size() == k)
                    return ans;
            }
        }
    }
};

这个是对出现频次排序，时间复杂度最坏的情况是O(nlogn)

class Solution {
public:
    static bool cmpSecond(pair<int, int> a, pair<int, int> b) {
        return a.second > b.second;
    }
    vector<int> topKFrequent(vector<int>& nums, int k) {
        vector<int> ans;
        if (nums.size() < 1)
            return ans;
        unordered_map<int, int> hashMap;
        for (auto x : nums)
            ++hashMap[x];
        //按数字出现的频次由大到小排序
        vector<pair<int, int>> tmp(hashMap.begin(), hashMap.end());
        sort(tmp.begin(), tmp.end(), cmpSecond);
        for (int i = 0; i < k; i++)
            ans.push_back(tmp[i].first);
        return ans;
    }
};