Skip to content

Commit c62d3a8

Browse files
linwtlinwt
committed
347.前K个高频元素，快速排序，堆排序，优先级队列
1 parent 9741932 commit c62d3a8

File tree

4 files changed

+185
-1
lines changed

4 files changed

+185
-1
lines changed

‎leetcode_Java/DoneTitle.txt

Lines changed: 1 addition & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -105,6 +105,7 @@
105105
316. 去除重复字母
106106
322. 零钱兑换
107107
338. 比特位计数
108+
347. 前 K 个高频元素
108109
392. 判断子序列
109110
394. 字符串解码
110111
402. 移掉 K 位数字

‎leetcode_Java/DoneType.txt

Lines changed: 1 addition & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -167,6 +167,7 @@
167167
287. 寻找重复数（哈希表，快慢指针，二分查找，位运算）
168168
303. 区域和检索 - 数组不可变（前缀和）
169169
304. 二维区域和检索 - 矩阵不可变（前缀和）
170+
347. 前 K 个高频元素（快速排序，堆排序，优先级队列）
170171
406. 根据身高重建队列（二维数组排序）
171172
448. 找到所有数组中消失的数字（计数，集合，置换）
172173
560. 和为 K 的子数组（前缀和，哈希表）

‎leetcode_Java/Solution0215.java

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -1,5 +1,5 @@
11
// 215. 数组中的第K个最大元素
2-
2+
// 主要思路同“347. 前 K 个高频元素”
33

44
/*
55
排序后取倒数第k个元素，api使用快速排序

‎leetcode_Java/Solution0347.java

Lines changed: 182 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,182 @@
1+
// 347. 前 K 个高频元素
2+
// 主要思路同“215. 数组中的第K个最大元素”
3+
4+
/*
5+
优先级队列，最小堆：
6+
1、统计元素的出现频率保存在map中
7+
2、优先级队列按照元素的频率 对元素升序排序，即小元素在队头，队列只保存最多k个元素
8+
3、遍历map，如果队列小于k，则直接将元素存入队列。否则跟队头元素比较频率，队头元素频率低则出栈，新元素入栈
9+
4、最终队列保存了前K个高频元素，转化成数组返回
10+
*/
11+
class Solution {
12+
public int[] topKFrequent(int[] nums, int k) {
13+
Map<Integer, Integer> map = new HashMap<>();
14+
for (int num : nums) {
15+
map.put(num, map.getOrDefault(num, 0) + 1);
16+
}
17+
PriorityQueue<Integer> queue = new PriorityQueue<>((a, b) -> map.get(a) - map.get(b));
18+
for(Integer num : map.keySet()) {
19+
if (queue.size() < k) {
20+
queue.add(num);
21+
} else if (map.get(num) > map.get(queue.peek())) {
22+
queue.remove();
23+
queue.add(num);
24+
}
25+
}
26+
int n = queue.size();
27+
int[] res = new int[n];
28+
for(int i = 0; i < n; i++) {
29+
res[i] = queue.poll();
30+
}
31+
return res;
32+
}
33+
}
34+
35+
36+
/*
37+
快速排序
38+
1、统计元素的出现频率保存在numToCountMap中，即 {元素：频率}
39+
2、将频率对应的元素保存在countToNumMap中，即 {频率：[元素1,元素2]}
40+
3、将频率保存在频率数组countArray中，对数组进行快速排序，得到频率第k大的索引
41+
4、遍历topk频率，找到对应的元素，加入结果数组中。要保证同一频率的元素优先取尽，且只取k个，结果数组不越界
42+
43+
与“215. 数组中的第K个最大元素”区别：
44+
1、本题需要对数组元素、频率处理。215题不需要
45+
2、本题排序方法返回的是第k大的元素的索引，再通过索引取前k个高频元素。215题排序方法直接返回第K个最大元素
46+
*/
47+
class Solution {
48+
public int[] topKFrequent(int[] nums, int k) {
49+
Map<Integer, Integer> numToCountMap = new HashMap<>();
50+
for (int num : nums) {
51+
numToCountMap.put(num, numToCountMap.getOrDefault(num, 0) + 1);
52+
}
53+
54+
Map<Integer, ArrayList<Integer>> countToNumMap = new HashMap<>();
55+
int n = numToCountMap.size();
56+
int index = 0;
57+
int[] countArray = new int[n];
58+
for (int num : numToCountMap.keySet()) {
59+
int count = numToCountMap.get(num);
60+
ArrayList<Integer> list = countToNumMap.getOrDefault(count, new ArrayList<Integer>());
61+
list.add(num);
62+
countToNumMap.put(count, list);
63+
countArray[index++] = count;
64+
}
65+
66+
int topkIndex = mainSort(countArray, 0, n - 1, n - k);
67+
int[] res = new int[k];
68+
index = 0;
69+
for (int i = topkIndex; i < n; i++) {
70+
ArrayList<Integer> list = countToNumMap.get(countArray[i]);
71+
while (list.size() > 0 && index < k) {
72+
res[index++] = list.get(0);
73+
list.remove(0);
74+
}
75+
}
76+
return res;
77+
}
78+
79+
private int mainSort(int[] nums, int left, int right, int target) {
80+
if (left == right) {
81+
return left;
82+
}
83+
int res;
84+
int mid = partition(nums, left, right);
85+
if (mid == target) {
86+
res = mid;
87+
} else if (mid > target) {
88+
res = mainSort(nums, left, mid - 1, target);
89+
} else {
90+
res = mainSort(nums, mid + 1, right, target);
91+
}
92+
return res;
93+
}
94+
95+
private int partition(int[] nums, int left, int right) {
96+
int index = left + 1;
97+
for (int i = index; i <= right; i++) {
98+
if (nums[i] < nums[left]) {
99+
swap(nums, i, index);
100+
index++;
101+
}
102+
}
103+
swap(nums, left, index - 1);
104+
return index - 1;
105+
}
106+
107+
private void swap(int[] nums, int x, int y) {
108+
int temp = nums[x];
109+
nums[x] = nums[y];
110+
nums[y] = temp;
111+
}
112+
}
113+
114+
115+
/*
116+
最大堆排序：思路同上，排序方法不同
117+
*/
118+
class Solution {
119+
public int[] topKFrequent(int[] nums, int k) {
120+
Map<Integer, Integer> numToCountMap = new HashMap<>();
121+
for (int num : nums) {
122+
numToCountMap.put(num, numToCountMap.getOrDefault(num, 0) + 1);
123+
}
124+
125+
Map<Integer, ArrayList<Integer>> countToNumMap = new HashMap<>();
126+
int n = numToCountMap.size();
127+
int index = 0;
128+
int[] countArray = new int[n];
129+
for (int num : numToCountMap.keySet()) {
130+
int count = numToCountMap.get(num);
131+
ArrayList<Integer> list = countToNumMap.getOrDefault(count, new ArrayList<Integer>());
132+
list.add(num);
133+
countToNumMap.put(count, list);
134+
countArray[index++] = count;
135+
}
136+
137+
int topkIndex = mainSort(countArray, k);
138+
int[] res = new int[k];
139+
index = 0;
140+
for (int i = topkIndex; i < n; i++) {
141+
ArrayList<Integer> list = countToNumMap.get(countArray[i]);
142+
while (list.size() > 0 && index < k) {
143+
res[index++] = list.get(0);
144+
list.remove(0);
145+
}
146+
}
147+
return res;
148+
}
149+
150+
public int mainSort(int[] nums, int k) {
151+
int n = nums.length;
152+
for (int i = n / 2 - 1; i >= 0; i--) {
153+
maxHeapify(nums, i, n);
154+
}
155+
while (n > 0 && k > 0) {
156+
swap(nums, 0, n - 1);
157+
n--;
158+
k--;
159+
maxHeapify(nums, 0, n);
160+
}
161+
return n;
162+
}
163+
164+
private void maxHeapify(int[] nums, int root, int n) {
165+
int maxIndex = root;
166+
int left = root * 2 + 1, right = root * 2 + 2;
167+
if (left < n && nums[left] > nums[maxIndex])
168+
maxIndex = left;
169+
if (right < n && nums[right] > nums[maxIndex])
170+
maxIndex = right;
171+
if (maxIndex != root) {
172+
swap(nums, maxIndex, root);
173+
maxHeapify(nums, maxIndex, n);
174+
}
175+
}
176+
177+
private void swap(int[] nums, int x, int y) {
178+
int temp = nums[x];
179+
nums[x] = nums[y];
180+
nums[y] = temp;
181+
}
182+
}

0 commit comments

Comments
 (0)