My code:
import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.PriorityQueue;
public class Solution {
public List<Integer> topKFrequent(int[] nums, int k) {
List<Integer> ret = new ArrayList<Integer>();
if (nums == null || nums.length == 0 || k < 1) {
return ret;
}
HashMap<Integer, Integer> map = new HashMap<Integer, Integer>();
for (int i = 0; i < nums.length; i++) {
if (!map.containsKey(nums[i])) {
map.put(nums[i], 1);
}
else {
map.put(nums[i], map.get(nums[i]) + 1);
}
}
PriorityQueue<Map.Entry<Integer, Integer>> pq = new PriorityQueue<Map.Entry<Integer, Integer>>(k, new Comparator<Map.Entry<Integer, Integer>>() {
public int compare(Map.Entry<Integer, Integer> i1, Map.Entry<Integer, Integer> i2) {
return i1.getValue().compareTo(i2.getValue());
}
});
for (Map.Entry<Integer, Integer> entry : map.entrySet()) {
pq.offer(entry);
if (pq.size() > k) {
pq.poll();
}
}
while (!pq.isEmpty()) {
ret.add(pq.poll().getKey());
}
Collections.sort(ret);
return ret;
}
public static void main(String[] args) {
Solution test = new Solution();
int[] nums = new int[]{5,2,5,3,5,3,1,1,3};
System.out.println(test.topKFrequent(nums, 2));
}
}
这道题目没能自己做出来，挺失望的。。。
看了答案；
reference:
https://discuss.leetcode.com/topic/44307/java-straightforward-o-n-n-k-lg-k-solution
我的思维是怎么样的？
我也想到了用 最小堆来做。但是最小堆的优先级是什么？应该是数字出现的频率。那么，最后的 k-heap，我们怎么把这些频率映射成我们需要的数字呢？如果多个数字出现的频率相同怎么办呢？
这会很麻烦，所以我放弃了。
于是看到了这个解法。
他也一定碰到了我的问题，并且以一种更好的方法解决了。
插入的是， Map.Entry
也就是说，我仍然以频率作为优先级，但是，我同时会保存住这个频率对应的数字。这样上面的问题就不存在了。
很巧妙。其实就是，
Priority index queue
时间复杂度应该是：
O(n log k)
空间复杂度是
O(k)
然后看到了一种更好的解法：
My code:
import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.PriorityQueue;
public class Solution {
public List<Integer> topKFrequent(int[] nums, int k) {
List<Integer> ret = new ArrayList<Integer>();
if (nums == null || nums.length == 0 || k < 1) {
return ret;
}
HashMap<Integer, Integer> map = new HashMap<Integer, Integer>();
for (int i = 0; i < nums.length; i++) {
if (!map.containsKey(nums[i])) {
map.put(nums[i], 1);
}
else {
map.put(nums[i], map.get(nums[i]) + 1);
}
}
List<Integer>[] bucket = new List[nums.length + 1];
for (Integer elem : map.keySet()) {
int times = map.get(elem);
if (bucket[times] == null) {
bucket[times] = new ArrayList<Integer>();
}
bucket[times].add(elem);
}
for (int i = bucket.length - 1; i >= 0; i--) {
if (bucket[i] != null) {
for (int j = 0; j < bucket[i].size(); j++) {
ret.add(bucket[i].get(j));
}
if (ret.size() >= k) {
return ret;
}
}
}
return ret;
}
public static void main(String[] args) {
Solution test = new Solution();
int[] nums = new int[]{5,2,5,3,5,3,1,1,3};
System.out.println(test.topKFrequent(nums, 2));
}
}
Bucket sort
reference:
https://discuss.leetcode.com/topic/44237/java-o-n-solution-bucket-sort
因为某个数字出现的频率，最多是 nums.length + 1.
所以，他们的范围可以被限定在， [1, nums.length + 1]之间
于是将出现频率相同的数字放在同一个bucket内部，用ArrayList相连。
最后完工。然后倒着遍历这个bucket array,
当 ret.size() < k 时，将bucket 某个index下List 里面所有的Integer全部塞进返回结果。
然后学到了一个新东西。
我们都知道， Java 泛型和数组不能混用。于是很多时候我们要么进行强制转换，要么用List代替纯Array
现在有了一个更好的方法：
List<Integer>[] block = new List<Integer>[n];
好吧，这真的是我第一次见到这样的写法。。。
Anyway, Good luck, Richardo! -- 09/14/2016
