E575 update 347 · githubniraj/Leetcode@4cb8292 · GitHub
[go: up one dir, main page]
Skip to content

Commit 4cb8292

Browse files
fishercoder1534fishercoder1534
committed
update 347
1 parent 76ee1ef commit 4cb8292

File tree

2 files changed

+32
-66
lines changed

2 files changed

+32
-66
lines changed

‎src/main/java/com/fishercoder/solutions/_347.java‎

Lines changed: 27 additions & 58 deletions
Original file line numberDiff line numberDiff line change
@@ -1,54 +1,53 @@
11
package com.fishercoder.solutions;
22

3-
import java.util.ArrayList;
4-
import java.util.HashMap;
5-
import java.util.List;
6-
import java.util.Map;
3+
import java.util.*;
74
import java.util.Map.Entry;
8-
import java.util.PriorityQueue;
9-
import java.util.Queue;
10-
import java.util.TreeMap;
115

126
public class _347 {
137

148
public static class Solution1 {
159
/**
16-
* Use buckets to hold numbers of the same frequency
17-
* It's averaged at 30 ms on Leetcode.
10+
* Bucket sort:
11+
* Use buckets to hold numbers of the same frequency, some buckets might be empty while the rest might have more than one element.
12+
* This editorial explains it well enough: https://leetcode.com/problems/top-k-frequent-elements/editorial/ starting from 08'55".
13+
* <p>
14+
* This is the most optimal solution.
15+
* Time: O(n)
16+
* Space: O(n)
1817
*/
1918
public int[] topKFrequent(int[] nums, int k) {
2019
Map<Integer, Integer> map = new HashMap();
21-
for (int i : nums) {
22-
map.put(i, map.getOrDefault(i, 0) + 1);
20+
for (int num : nums) {
21+
map.put(num, map.getOrDefault(num, 0) + 1);
2322
}
24-
25-
ArrayList[] bucket = new ArrayList[nums.length + 1];
26-
for (Entry<Integer, Integer> e : map.entrySet()) {
27-
int frequency = e.getValue();
28-
if (bucket[frequency] == null) {
29-
bucket[frequency] = new ArrayList<Integer>();
23+
//use nums.length + 1, so that we can directly use the frequency as the index for this array
24+
//how this buckets look like is: buckets[1] holds numbers that have frequency one, buckets[2] holds numbers that have frequency two, etc.
25+
//so, the numbers that have the highest frequencies are on the right-most side.
26+
List[] bucket = new ArrayList[nums.length + 1];
27+
for (Entry<Integer, Integer> entry : map.entrySet()) {
28+
int freq = entry.getValue();
29+
if (bucket[freq] == null) {
30+
bucket[freq] = new ArrayList<Integer>();
3031
}
31-
bucket[frequency].add(e.getKey());
32+
bucket[freq].add(entry.getKey());
3233
}
33-
List<Integer> result = new ArrayList<>();
34-
for (int i = bucket.length - 1; i >= 0 && result.size() < k; i--) {
34+
int[] result = new int[k];
35+
for (int i = bucket.length - 1, l = 0; i >= 0 && l < k; i--) {
3536
if (bucket[i] != null) {
3637
for (int j = 0; j < bucket[i].size(); j++) {
37-
result.add((int) bucket[i].get(j));
38+
result[l++] = (int) bucket[i].get(j);
3839
}
3940
}
4041
}
41-
int[] arr = new int[result.size()];
42-
for (int i = 0; i < arr.length; i++) {
43-
arr[i] = result.get(i);
44-
}
45-
return arr;
42+
return result;
4643
}
4744
}
4845

4946
public static class Solution2 {
5047
/**
51-
* Use hashtable and heap, it's averaged at 100 ms on Leetocde.
48+
* Use hashtable and heap.
49+
* Time: O(nlogn)
50+
* Space: O(n)
5251
*/
5352
public int[] topKFrequent(int[] nums, int k) {
5453
// construct the frequency map first, and then iterate through the map
@@ -58,7 +57,7 @@ public int[] topKFrequent(int[] nums, int k) {
5857
map.put(num, map.getOrDefault(num, 0) + 1);
5958
}
6059

61-
// build heap, this is O(logn)
60+
// build heap, this is O(nlogn)
6261
Queue<Entry<Integer, Integer>> heap = new PriorityQueue<>((o1, o2) -> o2.getValue() - o1.getValue());
6362
for (Entry<Integer, Integer> entry : map.entrySet()) {
6463
heap.offer(entry);
@@ -75,34 +74,4 @@ public int[] topKFrequent(int[] nums, int k) {
7574
return arr;
7675
}
7776
}
78-
79-
public static class Solution3 {
80-
/**
81-
* Use hashtable and heap, it's averaged at 10 ms on Leetocde.
82-
*/
83-
public int[] topKFrequent(int[] nums, int k) {
84-
Map<Integer, Integer> map = new HashMap<>();
85-
for (int i : nums) {
86-
map.put(i, map.getOrDefault(i, 0) + 1);
87-
}
88-
TreeMap<Integer, List<Integer>> treeMap = new TreeMap<>((a, b) -> b - a);
89-
for (int key : map.keySet()) {
90-
List<Integer> list = treeMap.getOrDefault(map.get(key), new ArrayList<>());
91-
list.add(key);
92-
treeMap.put(map.get(key), list);
93-
}
94-
List<Integer> list = new ArrayList<>();
95-
while (!treeMap.isEmpty()) {
96-
list.addAll(treeMap.pollFirstEntry().getValue());
97-
if (list.size() == k) {
98-
break;
99-
}
100-
}
101-
int[] ans = new int[list.size()];
102-
for (int i = 0; i < list.size(); i++) {
103-
ans[i] = list.get(i);
104-
}
105-
return ans;
106-
}
107-
}
10877
}

‎src/test/java/com/fishercoder/_347Test.java‎

Lines changed: 5 additions & 8 deletions
Original file line numberDiff line numberDiff line change
@@ -1,23 +1,21 @@
11
package com.fishercoder;
22

33
import com.fishercoder.solutions._347;
4-
import org.junit.BeforeClass;
5-
import org.junit.Test;
4+
import org.junit.jupiter.api.BeforeEach;
5+
import org.junit.jupiter.api.Test;
66

7-
import static org.junit.Assert.assertArrayEquals;
7+
import static org.junit.jupiter.api.Assertions.assertArrayEquals;
88

99
public class _347Test {
1010
private static _347.Solution1 solution1;
1111
private static _347.Solution2 solution2;
12-
private static _347.Solution3 solution3;
1312
private static int[] nums;
1413
private static int[] expected;
1514

16-
@BeforeClass
17-
public static void setup() {
15+
@BeforeEach
16+
public void setup() {
1817
solution1 = new _347.Solution1();
1918
solution2 = new _347.Solution2();
20-
solution3 = new _347.Solution3();
2119
}
2220

2321
@Test
@@ -43,7 +41,6 @@ public void test2() {
4341
public void test3() {
4442
nums = new int[]{3, 0, 1, 0};
4543
expected = new int[]{0, 3};
46-
//assertArrayEquals(expected, solution3.topKFrequent(nums, 2));
4744
}
4845

4946
@Test

0 commit comments

Comments
 (0)
0