1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

class Solution {
public:
    vector<int> topKFrequent(vector<int>& nums, int k) {
        unordered_map<int, int> umap;
        for (auto t : nums) {
            umap[t] ++;
        }

        priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> heap;
        for (auto t : umap) {
            if (heap.size() == k) {
                if (t.second > heap.top().first) {
                    heap.pop();
                    heap.push({t.second, t.first});
                }
            } else {
                heap.push({t.second, t.first});
            }
        }

        vector<int> res;
        while (k --) {
            auto t = heap.top();
            res.push_back(t.second);
            heap.pop();
        }
        return res;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 1e5 + 10;

int m, n;
int f[N], cnt;

void up(int u) {
    while (u / 2 && f[u / 2] > f[u]) {
        swap(f[u / 2], f[u]);
        u /= 2;
    }
}

void down(int u) {
    int t = u;
    if (u * 2 <= cnt && f[u * 2] < f[t]) t = u * 2;
    if (u * 2 + 1 <= cnt && f[u * 2 + 1] < f[t]) t = u * 2 + 1;
    if (u != t) {
        swap(f[u], f[t]);
        down(t);
    }
}

int main()
{
    cin >> n >> m;
    cnt = n;
    
    for (int i = 1; i <= n; i ++) cin >> f[i];
    
    for (int i = n / 2; i; i --) down(i);
    
    while (m --) {
        cout << f[1] << ' ';
        f[1] = f[cnt --];
        down(1);
    }
    
    return 0;
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

class Solution {
public:
    vector<int> topKFrequent(vector<int>& nums, int k) {
        unordered_map<int, int> umap;
        for (auto t : nums) {
            umap[t] ++;
        }

        vector<vector<int>> bucket(nums.size() + 1);
        for (auto t : umap) {
            bucket[t.second].push_back(t.first);
        }

        vector<int> res;
        for (int i = bucket.size() - 1; i >= 0 && res.size() < k; i --) {
            for (auto t : bucket[i]) {
                res.push_back(t);
                if (res.size() == k) break;
            }
        }
        return res;
    }
};