Skip to content

Commit 59e091b

Browse files
coderbruiscoderbruis
committed
[A] 添加TopK题解；[U] 更新readme
1 parent c65c26f commit 59e091b

2 files changed

Lines changed: 88 additions & 27 deletions

File tree

‎README.md‎

Lines changed: 27 additions & 27 deletions
Original file line numberDiff line numberDiff line change
@@ -7,15 +7,15 @@
77

88
# 经典排序算法
99

10-
- [冒泡排序](https://github.com/coderbruis/AlgorithmsInJava/blob/master/notes/algorithms/%E5%86%92%E6%B3%A1%E6%8E%92%E5%BA%8F%E7%AE%97%E6%B3%95.md)
11-
- [选择排序](https://github.com/coderbruis/AlgorithmsInJava/blob/master/notes/algorithms/%E9%80%89%E6%8B%A9%E6%8E%92%E5%BA%8F%E7%AE%97%E6%B3%95.md)
12-
- [插入排序](https://github.com/coderbruis/AlgorithmsInJava/blob/master/notes/algorithms/%E6%8F%92%E5%85%A5%E6%8E%92%E5%BA%8F%E7%AE%97%E6%B3%95.md)
13-
- [归并排序](https://github.com/coderbruis/AlgorithmsInJava/blob/master/notes/algorithms/%E5%BD%92%E5%B9%B6%E6%8E%92%E5%BA%8F%E7%AE%97%E6%B3%95.md)
14-
- [快速排序](https://github.com/coderbruis/AlgorithmsInJava/blob/master/notes/algorithms/%E5%BF%AB%E9%80%9F%E6%8E%92%E5%BA%8F%E7%AE%97%E6%B3%95.md)
15-
- [希尔排序](https://github.com/coderbruis/AlgorithmsInJava/blob/master/notes/algorithms/%E5%B8%8C%E5%B0%94%E6%8E%92%E5%BA%8F%E7%AE%97%E6%B3%95.md)
16-
- [桶排序](https://github.com/coderbruis/AlgorithmsInJava/blob/master/notes/algorithms/%E6%A1%B6%E6%8E%92%E5%BA%8F%E7%AE%97%E6%B3%95.md)
17-
- [基数排序](https://github.com/coderbruis/AlgorithmsInJava/blob/master/notes/algorithms/%E5%9F%BA%E6%95%B0%E6%8E%92%E5%BA%8F%E7%AE%97%E6%B3%95.md)
18-
- [堆排序](https://github.com/coderbruis/AlgorithmsInJava/blob/master/notes/algorithms/%E5%A0%86%E6%8E%92%E5%BA%8F%E7%AE%97%E6%B3%95.md)
10+
- [x] [冒泡排序](https://github.com/coderbruis/AlgorithmsInJava/blob/master/notes/algorithms/%E5%86%92%E6%B3%A1%E6%8E%92%E5%BA%8F%E7%AE%97%E6%B3%95.md)
11+
- [x] [选择排序](https://github.com/coderbruis/AlgorithmsInJava/blob/master/notes/algorithms/%E9%80%89%E6%8B%A9%E6%8E%92%E5%BA%8F%E7%AE%97%E6%B3%95.md)
12+
- [x] [插入排序](https://github.com/coderbruis/AlgorithmsInJava/blob/master/notes/algorithms/%E6%8F%92%E5%85%A5%E6%8E%92%E5%BA%8F%E7%AE%97%E6%B3%95.md)
13+
- [x] [归并排序](https://github.com/coderbruis/AlgorithmsInJava/blob/master/notes/algorithms/%E5%BD%92%E5%B9%B6%E6%8E%92%E5%BA%8F%E7%AE%97%E6%B3%95.md)
14+
- [x] [快速排序](https://github.com/coderbruis/AlgorithmsInJava/blob/master/notes/algorithms/%E5%BF%AB%E9%80%9F%E6%8E%92%E5%BA%8F%E7%AE%97%E6%B3%95.md)
15+
- [x] [希尔排序](https://github.com/coderbruis/AlgorithmsInJava/blob/master/notes/algorithms/%E5%B8%8C%E5%B0%94%E6%8E%92%E5%BA%8F%E7%AE%97%E6%B3%95.md)
16+
- [x] [桶排序](https://github.com/coderbruis/AlgorithmsInJava/blob/master/notes/algorithms/%E6%A1%B6%E6%8E%92%E5%BA%8F%E7%AE%97%E6%B3%95.md)
17+
- [x] [基数排序](https://github.com/coderbruis/AlgorithmsInJava/blob/master/notes/algorithms/%E5%9F%BA%E6%95%B0%E6%8E%92%E5%BA%8F%E7%AE%97%E6%B3%95.md)
18+
- [x] [堆排序](https://github.com/coderbruis/AlgorithmsInJava/blob/master/notes/algorithms/%E5%A0%86%E6%8E%92%E5%BA%8F%E7%AE%97%E6%B3%95.md)
1919

2020
## 排序算法总结
2121

@@ -50,27 +50,27 @@
5050
# 经典算法
5151

5252

53-
- KMP算法
54-
- 马拉车算法
55-
- Prim算法
56-
- Krusk算法
57-
- Dijkstra算法
58-
- Bellman-Ford算法
53+
- [ ] KMP算法
54+
- [ ] 马拉车算法
55+
- [ ] Prim算法
56+
- [ ] Krusk算法
57+
- [ ] Dijkstra算法
58+
- [ ] Bellman-Ford算法
5959

6060
# 经典数据结构
6161
62-
- 数组
63-
- 栈和队列
64-
- 链表
65-
- 二分搜索树
66-
- 集合和映射
67-
- [堆和优先队列](https://github.com/coderbruis/AlgorithmsInJava/blob/master/notes/datastructures/%E5%A0%86%E5%92%8C%E4%BC%98%E5%85%88%E9%98%9F%E5%88%97.md) 【更新中】
68-
- 线段树
69-
- Trie树
70-
- 并查集
71-
- [AVL树](https://github.com/coderbruis/AlgorithmsInJava/blob/master/notes/datastructures/AVL%E6%A0%91.md)【更新中】
72-
- 红黑树
73-
- 哈希表
62+
- [ ] 数组
63+
- [ ] 栈和队列
64+
- [ ] 链表
65+
- [ ] 二分搜索树
66+
- [ ] 集合和映射
67+
- [x] [堆和优先队列](https://github.com/coderbruis/AlgorithmsInJava/blob/master/notes/datastructures/%E5%A0%86%E5%92%8C%E4%BC%98%E5%85%88%E9%98%9F%E5%88%97.md)
68+
- [ ] 线段树
69+
- [ ] Trie树
70+
- [ ] 并查集
71+
- [x] [AVL树](https://github.com/coderbruis/AlgorithmsInJava/blob/master/notes/datastructures/AVL%E6%A0%91.md)
72+
- [ ] 红黑树
73+
- [ ] 哈希表
7474

7575
==================== 持续更新 ===================
7676

‎src/main/java/com/bruis/algorithminjava/algorithm/leetcode/array/TopKFrequentElements.java‎

Lines changed: 61 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,61 @@
1+
package com.bruis.algorithminjava.algorithm.leetcode.array;
2+
3+
import java.util.*;
4+
5+
/**
6+
*
7+
* 前K个高频元素
8+
*
9+
* url：https://leetcode-cn.com/problems/top-k-frequent-elements/
10+
*
11+
* @author LuoHaiYang
12+
*/
13+
public class TopKFrequentElements {
14+
15+
/**
16+
*
17+
*
18+
*
19+
*/
20+
public int[] topKFrequent(int[] nums, int k) {
21+
if (nums == null || nums.length < 2) {
22+
return nums;
23+
}
24+
Map<Integer, Integer> count = new LinkedHashMap<>();
25+
int n = nums.length;
26+
27+
for (int i = 0; i < n; i++) {
28+
if (count.containsKey(nums[i])) {
29+
count.put(nums[i], count.get(nums[i]) + 1);
30+
} else {
31+
count.put(nums[i], 1);
32+
}
33+
}
34+
35+
List<Integer> result = new ArrayList<>();
36+
37+
Set<Map.Entry<Integer, Integer>> entries = count.entrySet();
38+
39+
for (Map.Entry<Integer, Integer> entry : entries) {
40+
if (entry.getValue() > k) {
41+
result.add(entry.getKey());
42+
}
43+
}
44+
45+
46+
int[] res = new int[result.size()];
47+
48+
for (int i = 0; i < result.size(); i++) {
49+
res[i] = result.get(i);
50+
}
51+
return res.length > 0 ? res : nums;
52+
}
53+
54+
public static void main(String[] args) {
55+
TopKFrequentElements topKFrequentElements = new TopKFrequentElements();
56+
//int[] test = {1,1,1,2,2,3};
57+
int[] test = {3,0,1,0};
58+
topKFrequentElements.topKFrequent(test,1);
59+
60+
}
61+
}

0 commit comments

Comments
 (0)