解法1
- 向PriorityQueue传入可比较的Freq；
- Java中提供的PriorityQueue底层维护的是个最小堆，这会影响到Freq对Comparable接口中compareTo(Freq another)方法的实现；
package leetcode._347;
import java.util.ArrayList;
import java.util.List;
import java.util.PriorityQueue;
import java.util.TreeMap;
public class Solution2 {
private class Freq implements Comparable<Freq>{
public int e, freq;
public Freq(int e, int freq) {
this.e = e;
this.freq = freq;
}
@Override
public int compareTo(Freq another) {
if (this.freq < another.freq) {
return -1;
} else if (this.freq > another.freq) {
return 1;
} else {
return 0;
}
}
}
public List<Integer> topKFrequent(int[] nums, int k) {
TreeMap<Integer, Integer> map = new TreeMap<>();
for (int num : nums) {
if (map.containsKey(num)) {
map.put(num, map.get(num) + 1);
} else {
map.put(num, 1);
}
}
PriorityQueue<Freq> priorityQueue = new PriorityQueue<>();
for (int key : map.keySet()) {
if (priorityQueue.size() < k) {
priorityQueue.add(new Freq(key, map.get(key)));
} else {
if (map.get(key) > priorityQueue.peek().freq) {
priorityQueue.remove();
priorityQueue.add(new Freq(key, map.get(key)));
}
}
}
ArrayList<Integer> list = new ArrayList<>();
while (!priorityQueue.isEmpty()) {
list.add(priorityQueue.remove().e);
}
return list;
}
}
解法2
- 通过实现一个FreqComparator类，定义（或重定义）Freq的比较规则；
- 这种方式可以重定义String类的比较规则；
package leetcode._347;
import java.util.*;
public class Solution3 {
private class Freq {
public int e, freq;
public Freq(int e, int freq) {
this.e = e;
this.freq = freq;
}
}
private class FreqComparator implements Comparator<Freq> {
@Override
public int compare(Freq a, Freq b) {
return a.freq - b.freq;
}
}
public List<Integer> topKFrequent(int[] nums, int k) {
TreeMap<Integer, Integer> map = new TreeMap<>();
for (int num : nums) {
if (map.containsKey(num)) {
map.put(num, map.get(num) + 1);
} else {
map.put(num, 1);
}
}
PriorityQueue<Freq> priorityQueue = new PriorityQueue<>(new FreqComparator());
for (int key : map.keySet()) {
if (priorityQueue.size() < k) {
priorityQueue.add(new Freq(key, map.get(key)));
} else {
if (map.get(key) > priorityQueue.peek().freq) {
priorityQueue.remove();
priorityQueue.add(new Freq(key, map.get(key)));
}
}
}
ArrayList<Integer> list = new ArrayList<>();
while (!priorityQueue.isEmpty()) {
list.add(priorityQueue.remove().e);
}
return list;
}
}
解法3
- 使用匿名内部类代替显示定义FreqComparator的方法；
package leetcode._347;
import java.util.*;
public class Solution4 {
private class Freq {
public int e, freq;
public Freq(int e, int freq) {
this.e = e;
this.freq = freq;
}
}
public List<Integer> topKFrequent(int[] nums, int k) {
TreeMap<Integer, Integer> map = new TreeMap<>();
for (int num : nums) {
if (map.containsKey(num)) {
map.put(num, map.get(num) + 1);
} else {
map.put(num, 1);
}
}
PriorityQueue<Freq> priorityQueue = new PriorityQueue<>(new Comparator<Freq>() {
@Override
public int compare(Freq a, Freq b) {
return a.freq - b.freq;
}
});
for (int key : map.keySet()) {
if (priorityQueue.size() < k) {
priorityQueue.add(new Freq(key, map.get(key)));
} else {
if (map.get(key) > priorityQueue.peek().freq) {
priorityQueue.remove();
priorityQueue.add(new Freq(key, map.get(key)));
}
}
}
ArrayList<Integer> list = new ArrayList<>();
while (!priorityQueue.isEmpty()) {
list.add(priorityQueue.remove().e);
}
return list;
}
}
解法4
- 通过向PriorityQueue中只存入key，代替存入键值对，从而省略了Freq的定义；
package leetcode._347;
import java.util.*;
public class Solution5 {
public List<Integer> topKFrequent(int[] nums, int k) {
TreeMap<Integer, Integer> map = new TreeMap<>();
for (int num : nums) {
if (map.containsKey(num)) {
map.put(num, map.get(num) + 1);
} else {
map.put(num, 1);
}
}
PriorityQueue<Integer> priorityQueue = new PriorityQueue<>(new Comparator<Integer>() {
@Override
public int compare(Integer a, Integer b) {
return map.get(a) - map.get(b);
}
});
for (int key : map.keySet()) {
if (priorityQueue.size() < k) {
priorityQueue.add(key);
} else {
if (map.get(key) > map.get(priorityQueue.peek())) {
priorityQueue.remove();
priorityQueue.add(key);
}
}
}
ArrayList<Integer> list = new ArrayList<>();
while (!priorityQueue.isEmpty()) {
list.add(priorityQueue.remove());
}
return list;
}
}
解法5
package leetcode._347;
import java.util.*;
public class Solution6 {
public List<Integer> topKFrequent(int[] nums, int k) {
TreeMap<Integer, Integer> map = new TreeMap<>();
for (int num : nums) {
if (map.containsKey(num)) {
map.put(num, map.get(num) + 1);
} else {
map.put(num, 1);
}
}
PriorityQueue<Integer> priorityQueue = new PriorityQueue<>(
(a, b) -> map.get(a) - map.get(b)
);
for (int key : map.keySet()) {
if (priorityQueue.size() < k) {
priorityQueue.add(key);
} else {
if (map.get(key) > map.get(priorityQueue.peek())) {
priorityQueue.remove();
priorityQueue.add(key);
}
}
}
ArrayList<Integer> list = new ArrayList<>();
while (!priorityQueue.isEmpty()) {
list.add(priorityQueue.remove());
}
return list;
}
}
