# 前 K 个高频元素

<p>给你一个整数数组 <code>nums</code> 和一个整数 <code>k</code> ，请你返回其中出现频率前 <code>k</code> 高的元素。你可以按 <strong>任意顺序</strong> 返回答案。</p>

<p> </p>

<p><strong>示例 1:</strong></p>

<pre>
<strong>输入: </strong>nums = [1,1,1,2,2,3], k = 2
<strong>输出: </strong>[1,2]
</pre>

<p><strong>示例 2:</strong></p>

<pre>
<strong>输入: </strong>nums = [1], k = 1
<strong>输出: </strong>[1]</pre>

<p> </p>

<p><strong>提示：</strong></p>

<ul>
	<li><code>1 <= nums.length <= 10<sup>5</sup></code></li>
	<li><code>k</code> 的取值范围是 <code>[1, 数组中不相同的元素的个数]</code></li>
	<li>题目数据保证答案唯一，换句话说，数组中前 <code>k</code> 个高频元素的集合是唯一的</li>
</ul>

<p> </p>

<p><strong>进阶：</strong>你所设计算法的时间复杂度 <strong>必须</strong> 优于 <code>O(n log n)</code> ，其中 <code>n</code><em> </em>是数组大小。</p>

<p>以下错误的选项是？</p>

## aop

### before

```cpp
#include <bits/stdc++.h>
using namespace std;
```
### after

```cpp
int main()
{
    Solution sol;
    vector<int> nums = {1, 1, 1, 2, 2, 3};
    int k = 2;
    vector<int> res;
    res = sol.topKFrequent(nums, k);
    for (auto i : res)
        cout << i << " ";
    return 0;
}
```

## 答案

```cpp
class Solution
{
public:
    vector<int> topKFrequent(vector<int> &nums, int k)
    {
        sort(nums.begin(), nums.end());
        vector<pair<int, int>> cnt;
        for (int i = 0; i < nums.size();)
        {
            int count = 1;
            while (i + count < nums.size())
                count++;
            cnt.push_back({nums[i], count});
            i += count;
        }
        sort(cnt.begin(), cnt.end(), cmp);
        vector<int> ans(k);
        for (int i = 0; i < k; i++)
            ans[i] = cnt[i].first;
        return ans;
    }
};
```

## 选项


### A

```cpp
class Solution
{
public:
    vector<int> topKFrequent(vector<int> &nums, int k)
    {
        unordered_map<int, int> freq;
        for (int i = 0; i < nums.size(); i++)
        {
            freq[nums[i]]++;
        }

        priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;

        for (auto a : freq)
        {
            if (pq.size() == k)
            {
                if (a.second > pq.top().first)
                {
                    pq.pop();
                    pq.push(make_pair(a.second, a.first));
                }
            }
            else
            {
                pq.push(make_pair(a.second, a.first));
            }
        }
        vector<int> res;
        while (!pq.empty())
        {
            res.push_back(pq.top().second);
            pq.pop();
        }
        return res;
    }
};
```

### B

```cpp
class Solution
{
public:
    static bool cmp(const vector<int> &a, const vector<int> &b)
    {
        return a[1] > b[1];
    }
    vector<int> topKFrequent(vector<int> &nums, int k)
    {
        vector<int> a;
        map<int, int> list1;
        for (int i = 0; i < nums.size(); i++)
        {
            if (!list1.count(nums[i]))
            {
                list1.insert(map<int, int>::value_type(nums[i], 1));
                a.push_back(nums[i]);
            }
            else
            {
                list1[nums[i]]++;
            }
        }
        vector<vector<int>> b(a.size(), vector<int>(2));
        for (int i = 0; i < a.size(); i++)
        {
            b[i][0] = a[i];
            b[i][1] = list1[a[i]];
        }
        sort(b.begin(), b.end(), cmp);
        a.clear();
        for (int i = 0; i < k; i++)
        {
            a.push_back(b[i][0]);
        }
        return a;
    }
};
```

### C

```cpp
class Solution
{
public:
    vector<int> topKFrequent(vector<int> &nums, int k)
    {

        unordered_map<int, int> nums_count;
        for (auto x : nums)
        {
            nums_count[x]++;
        }

        multimap<int, int, greater<int>> big_m;
        for (auto x : nums_count)
        {
            big_m.insert(make_pair(x.second, x.first));
        }

        vector<int> res;
        for (auto it = big_m.begin(); it != big_m.end() && k; it++, k--)
        {
            res.push_back(it->second);
        }
        return res;
    }
};
```