[Leetcode]347. Top K Frequent Elements(C++)

题目描述

Given an integer array nums and an integer k, return the k most frequent elements. You may return the answer in any order.

例子

例子 1

Input: nums = [1,1,1,2,2,3], k = 2 Output: [1,2]

例子 2

Input: nums = [1], k = 1 Output: [1]

Constraints

1 <= nums.length <= 10^5

k is in the range [1, the number of unique elements in the array].

It is guaranteed that the answer is unique.

解题思路

这道题可以分为两部分：计算各元素的出现频率，选出频率前 k 的元素。这两部分都比较简单，可以用哈希表来计算频率统计的计算，而用优先队列来筛选频率前 k 高的元素。注意一下对非标准元素的优先队列的使用方法即可（这里是 std::pair<int, int>）。代码如下：

#include <queue>
#include <unordered_map>

class Solution {
public:
    std::vector<int> topKFrequent(std::vector<int>& nums, int k) {
        std::unordered_map<int, int> hmap;
        for (int num : nums) {
            if (hmap.find(num) == hmap.end()) {
                hmap[num] = 1;
            } else {
                hmap[num]++;
            }
        }

        using key_freq = std::pair<int, int>;
        auto comp = [](const key_freq& lhs, const key_freq& rhs) {
            return lhs.second >= rhs.second;
        };
        std::priority_queue<key_freq, std::vector<key_freq>, decltype(comp)> pq(
            comp);

        for (auto it : hmap) {
            pq.push({it.first, it.second});
            if (pq.size() > k) {
                pq.pop();
            }
        }

        std::vector<int> ret;
        while (!pq.empty()) {
            ret.push_back(pq.top().first);
            pq.pop();
        }

        return ret;
    }
};

时间复杂度: O(max(n, unique(nums) log k)) – 哈希表处理过程为 O(n), 优先队列插入过程单次为 O(log k) 插入次数为数组中不重复元素的个数
空间复杂度: O(n)

GitHub 代码同步地址： 347.TopKFrequentElements.cpp

其他题目： GitHub: Leetcode-C++-Solution 博客： Leetcode-Solutions