前 K 个高频元素

问题描述

给定一个非空的整数数组，返回其中出现频率前 k 高的元素。

示例 1:
输入: nums = [1,1,1,2,2,3], k = 2
输出: [1,2]

示例 2:
输入: nums = [1], k = 1
输出: [1]

说明：
你可以假设给定的 k 总是合理的，且 1 ≤ k ≤ 数组中不相同的元素的个数。
你的算法的时间复杂度必须优于 O(n log n) , n 是数组的大小。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/top-k-frequent-elements

思路

首先，在元素与元素出现次数之间建立一个map映射；
然后申请一个pair<int,int>类型的vector，并将这些映射关系存入到vector中。
将vector中元素按照second（元素出现次数）从大到小排序。
最后，将前k个pair元素的first（元素值）存入到一个vector即可。

题解

class Solution {
public:
    static bool cmp(const std::pair<int, int> &left, const std::pair<int, int> &right) {
        return left.second > right.second;
    }
    vector<int> topKFrequent(vector<int> &nums, int k) {
        std::map<int, int> count;
        for(int i=0;i<nums.size();i++) count[nums[i]]++;
        vector<pair<int, int>> buf;
        for(auto each:count) buf.push_back(each);
        sort(buf.begin(), buf.end(), cmp);
        vector<int> ans;
        for (auto each:buf) {
            if (ans.size() < k) {
                ans.push_back(each.first);
            }
        }
        return ans;
    }
};