leetcode347:前K个高频元素

题目链接

leetcode

题目描述

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

C++ 代码

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
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
#include <iostream>
#include <vector>
#include <queue>
#include <unordered_map>
#include <algorithm>
using namespace std;

/*
哈希表 + 堆
自定义堆中保存的结构体(定义成员、定义比较规则)

时间复杂度:O(nlogk)
n 为数组的长度,k 为高频元素的个数。
空间复杂度:O(n)
哈希表的大小为 O(n),堆的大小为 O(k),共计为 O(n)。
*/
class Solution_0 {
public:
vector<int> topKFrequent(vector<int>& nums, int k) {
for (const int& num : nums) {
num2cnt[num]++;
}

for (const auto& it : num2cnt) {
heap.push({it.second, it.first});
if (heap.size() > k) {
heap.pop();
}
}

vector<int> res;
res.reserve(k);
while (!heap.empty()) {
Node node = heap.top(); heap.pop();
res.push_back(node.num);
}
reverse(res.begin(), res.end()); // 升序排列

return res;
}

private:
struct Node {
int cnt;
int num;
bool operator<(const Node& t) const {
if (cnt != t.cnt) return cnt > t.cnt;
return num < t.num;
}
};

priority_queue<Node> heap; // 大根堆
unordered_map<int, int> num2cnt; // 哈希表
};

/*
思路同上
堆中保存元素类型是 pair<int, int>,
自定义 priority_queue 排序规则

时间复杂度:O(nlogk)
空间复杂度:O(n)
*/
class Solution {
public:
vector<int> topKFrequent(vector<int>& nums, int k) {
unordered_map<int, int> num2cnt;
for (const int& num : nums) {
num2cnt[num]++;
}

priority_queue<pair<int, int>, vector<pair<int, int>>, decltype(&cmp)> heap(cmp);
for (const auto& it : num2cnt) {
int num = it.first, cnt = it.second;
heap.push({num, cnt});
if (heap.size() > k) {
heap.pop();
}
}

// vector<int> res;
// res.reserve(k);
// while (!heap.empty()) {
// res.emplace_back(heap.top().first);
// heap.pop();
// }
// reverse(res.begin(), res.end()); // 升序排列
vector<int> res(k);
int i = k-1;
while (!heap.empty()) {
res[i] = heap.top().first;
heap.pop();
i--;
}

return res;
}

private:
static bool cmp(pair<int, int>& a, pair<int, int>& b) {
return a.second > b.second;
}
};

// 辅助函数:打印数组
void printArray(const vector<int>& nums) {
cout << "[";
for (size_t i = 0; i < nums.size(); i++) {
cout << nums[i];
if (i != nums.size() - 1) cout << ",";
}
cout << "]";
}

int main() {
Solution solution;
vector<vector<int>> nums_cases = {
{1,1,1,2,2,3},
{1}
};
vector<int> k_cases = {
2, 1
};

for (int i = 0; i < nums_cases.size(); i++) {
auto& nums = nums_cases[i];
int k = k_cases[i];

cout << "Input: nums = ";
printArray(nums);
cout << ", k = " << k << endl;
vector<int> result = solution.topKFrequent(nums, k);
cout << "Output: ";
printArray(result);
cout << endl;
}

return 0;
}

leetcode347:前K个高频元素
https://lcf163.github.io/2024/05/15/leetcode347:前K个高频元素/
作者
乘风的小站
发布于
2024年5月15日
许可协议