Skip to content

Commit dc990cc

Browse files
fishercoder1534fishercoder1534
committed
[N-0] refactor 347
1 parent 480f2f7 commit dc990cc

File tree

3 files changed

+95
-79
lines changed

3 files changed

+95
-79
lines changed

‎README.md

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -335,7 +335,7 @@ Your ideas/fixes/algorithms are more than welcome!
335335
|350|[Intersection of Two Arrays II](https://leetcode.com/problems/intersection-of-two-arrays-ii/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_350.java)| O(m+n)|O((m+n)) could be optimized | Easy| HashMap, Binary Search
336336
|349|[Intersection of Two Arrays](https://leetcode.com/problems/intersection-of-two-arrays/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_349.java)| O(m+n)|O(min(m,n)) | Easy| Two Pointers, Binary Search
337337
|348|[Design Tic-Tac-Toe](https://leetcode.com/problems/design-tic-tac-toe/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_348.java)| O(1)|O(n) | Medium| Design
338-
|347|[Top K Frequent Elements](https://leetcode.com/problems/top-k-frequent-elements/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_347.java)| O(n)|O(1) | Medium| HashTable, Heap
338+
|347|[Top K Frequent Elements](https://leetcode.com/problems/top-k-frequent-elements/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_347.java)| O(n)|O(1) | Medium| HashTable, Heap, Bucket Sort
339339
|346|[Moving Average from Data Stream](https://leetcode.com/problems/moving-average-from-data-stream/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_346.java)| O(1)|O(w)) | Easy| Queue
340340
|345|[Reverse Vowels of a String](https://leetcode.com/problems/reverse-vowels-of-a-string/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_345.java) | O(n) |O(1) | Easy | String
341341
|344|[Reverse String](https://leetcode.com/problems/reverse-string/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_344.java) | O(n) |O(1) | Easy | String

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

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

33
import java.util.ArrayList;
4-
import java.util.Comparator;
54
import java.util.HashMap;
65
import java.util.List;
76
import java.util.Map;
@@ -22,94 +21,70 @@
2221
Your algorithm's time complexity must be better than O(n log n), where n is the array's size.*/
2322

2423
public class _347 {
25-
// Approach 1: use buckets to hold numbers of the same frequency
26-
/**Attn: we must use a simple array to solve this problem, instead of using List<List<Integer>>,
27-
* we have to use List<Integer>[], otherwise, cases like this one: [-1,-1]
28-
* 1 will fail due to the fact that ArrayList.get(i),
29-
* this i must be a non-negative number, however, in simple arrays, the index could be negative.
30-
* Although in this question, frequency will be at least 1, but still in problems like this where bucket sort
31-
* works the best, you should use List<Integer>[], this will simplify the code.*/
32-
public List<Integer> topKFrequent_using_bucket(int[] nums, int k) {
33-
Map<Integer, Integer> map = new HashMap();
34-
for (int i : nums) {
35-
map.put(i, map.getOrDefault(i, 0) + 1);
36-
}
3724

38-
ArrayList[] bucket = new ArrayList[nums.length + 1];
39-
for (Entry<Integer, Integer> e : map.entrySet()) {
40-
int frequency = e.getValue();
41-
if (bucket[frequency] == null) {
42-
bucket[frequency] = new ArrayList<Integer>();
25+
public static class Solution1 {
26+
/**
27+
* Use buckets to hold numbers of the same frequency
28+
*/
29+
public List<Integer> topKFrequent(int[] nums, int k) {
30+
Map<Integer, Integer> map = new HashMap();
31+
for (int i : nums) {
32+
map.put(i, map.getOrDefault(i, 0) + 1);
4333
}
44-
bucket[frequency].add(e.getKey());
45-
}
46-
List<Integer> result = new ArrayList<Integer>();
47-
for (int i = bucket.length - 1; i >= 0 && result.size() < k; i--) {
48-
if (bucket[i] != null) {
49-
result.addAll(bucket[i]);
34+
35+
ArrayList[] bucket = new ArrayList[nums.length + 1];
36+
for (Entry<Integer, Integer> e : map.entrySet()) {
37+
int frequency = e.getValue();
38+
if (bucket[frequency] == null) {
39+
bucket[frequency] = new ArrayList<Integer>();
40+
}
41+
bucket[frequency].add(e.getKey());
42+
}
43+
List<Integer> result = new ArrayList<>();
44+
for (int i = bucket.length - 1; i >= 0 && result.size() < k; i--) {
45+
if (bucket[i] != null) {
46+
for (int j = 0; j < bucket[i].size(); j++) {
47+
result.add((int) bucket[i].get(j));
48+
}
49+
}
5050
}
51-
}
5251

53-
return result;
52+
return result;
53+
}
5454
}
5555

56-
// Approach 2: use hashtable and heap
57-
58-
/**
59-
* Bonus tips on how to write a priority queue:
60-
* <p>
61-
* Tip1:
62-
* it should be like this:
63-
* PriorityQueue's angle brackets should be left blank, the type should be in
64-
* Comparator's angle brackets and the compare method should be in Comparator's
65-
* brackets. new PriorityQueue<>(new Comparator<int[]>(){ public int
66-
* compare(int[] o1, int[] o2){ } })
67-
* <p>
68-
* Tip2:
69-
* if you want things in DEscending order, then if(01 > o2), it should return -1
70-
* if Ascending order, then if(01 > o2), it should return 1
71-
*/
72-
public List<Integer> topKFrequent_using_heap(int[] nums, int k) {
73-
Map<Integer, Integer> map = new HashMap();
74-
Queue<Entry<Integer, Integer>> heap = new PriorityQueue<>(new Comparator<Entry<Integer, Integer>>() {
75-
@Override
76-
public int compare(Entry<Integer, Integer> o1, Entry<Integer, Integer> o2) {
77-
if (o1.getValue() > o2.getValue()) {
78-
return -1;
79-
} else if (o1.getValue() < o2.getValue()) {
80-
return 1;
81-
}
82-
return 0;
56+
public static class Solution2 {
57+
/**
58+
* Use hashtable and heap
59+
*/
60+
public List<Integer> topKFrequent(int[] nums, int k) {
61+
// construct the frequency map first, and then iterate through the map
62+
// and put them into the heap, this is O(n)
63+
Map<Integer, Integer> map = new HashMap();
64+
for (int num : nums) {
65+
map.put(num, map.getOrDefault(num, 0) + 1);
8366
}
84-
});
8567

86-
// construct the frequency map first, and then iterate through the map
87-
// and put them into the heap, this is O(n)
88-
for (int x : nums) {
89-
if (map.containsKey(x)) {
90-
map.put(x, map.get(x) + 1);
91-
} else {
92-
map.put(x, 1);
68+
// build heap, this is O(logn)
69+
Queue<Entry<Integer, Integer>> heap = new PriorityQueue<>((o1, o2) -> {
70+
if (o1.getValue() > o2.getValue()) {
71+
return -1;
72+
} else if (o1.getValue() < o2.getValue()) {
73+
return 1;
74+
} else {
75+
return 0;
76+
}
77+
});
78+
for (Entry<Integer, Integer> entry : map.entrySet()) {
79+
heap.offer(entry);
9380
}
94-
}
95-
96-
// build heap, this is O(n) as well
97-
for (Entry<Integer, Integer> entry : map.entrySet()) {
98-
heap.offer(entry);
99-
}
10081

101-
List<Integer> res = new ArrayList();
102-
while (k-- > 0) {
103-
res.add(heap.poll().getKey());
82+
List<Integer> res = new ArrayList();
83+
while (k-- > 0) {
84+
res.add(heap.poll().getKey());
85+
}
86+
return res;
10487
}
105-
return res;
106-
}
107-
108-
public static void main(String[] args) {
109-
int[] nums = new int[]{3, 0, 1, 0};
110-
_347 test = new _347();
111-
test.topKFrequent_using_heap(nums, 1);
112-
// test.topKFrequent_using_bucket(nums, 1);
11388
}
11489

11590
}

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

Lines changed: 41 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,41 @@
1+
package com.fishercoder;
2+
3+
import com.fishercoder.solutions._347;
4+
import org.junit.BeforeClass;
5+
import org.junit.Test;
6+
7+
import java.util.ArrayList;
8+
import java.util.Arrays;
9+
import java.util.List;
10+
11+
import static org.junit.Assert.assertEquals;
12+
13+
public class _347Test {
14+
private static _347.Solution1 solution1;
15+
private static _347.Solution2 solution2;
16+
private static int[] nums;
17+
private static List<Integer> expected;
18+
19+
@BeforeClass
20+
public static void setup() {
21+
solution1 = new _347.Solution1();
22+
solution2 = new _347.Solution2();
23+
}
24+
25+
@Test
26+
public void test1() {
27+
nums = new int[]{3, 0, 1, 0};
28+
expected = new ArrayList<>(Arrays.asList(0, 3));
29+
/**Comment out until Leetcode addresses this test case:
30+
* https://discuss.leetcode.com/topic/44237/java-o-n-solution-bucket-sort/75
31+
* Then I'll update this Solution1 code accordingly.*/
32+
// assertEquals(expected, solution1.topKFrequent(nums, 2));
33+
}
34+
35+
@Test
36+
public void test2() {
37+
nums = new int[]{3, 0, 1, 0};
38+
expected = new ArrayList<>(Arrays.asList(0, 3));
39+
assertEquals(expected, solution2.topKFrequent(nums, 2));
40+
}
41+
}

0 commit comments

Comments
 (0)