題目
Given a non-empty array of integers, return the k most frequent elements.
Example 1:
Input: nums = [1,1,1,2,2,3], k = 2
Output: [1,2]
Example 2:
Input: nums = [1], k = 1
Output: [1]
Note:
- You may assume k is always valid, 1 ≤ k ≤ number of unique elements.
- Your algorithm's time complexity must be better than O(n log n), where n is the array's size.
解法思路（一）
- 先用 HashMap 統(tǒng)計(jì)詞頻；
- 再維護(hù)一個(gè)容量為 k 的最小堆，里面存的結(jié)構(gòu)是頻率和數(shù)字的鍵值對(duì)，最小堆中的元素個(gè)數(shù)還沒到 k 就繼續(xù)往里面扔元素；到了就看要新添的元素能不能把堆頂?shù)脑財(cái)D掉，使堆維護(hù)的 k 個(gè)元素都是目前頻率最高的 k 個(gè)元素；
解法實(shí)現(xiàn)（一）
時(shí)間復(fù)雜度
- O(NlogK)；
空間復(fù)雜度
- O(N + K)；
關(guān)鍵字
優(yōu)先隊(duì)列 最小堆 詞頻統(tǒng)計(jì) HashMap
實(shí)現(xiàn)細(xì)節(jié)
-
PriorityQueue在實(shí)例化的時(shí)候，要傳入一個(gè)比較器new PairComparator()，比較器PairComparator的實(shí)現(xiàn)不用太較真，關(guān)于正負(fù)，一次沒寫對(duì)，換一下就行了；
package leetcode._347;
import javafx.util.Pair;
import java.util.*;
public class Solution347_1 {
private class PairComparator implements Comparator<Pair<Integer, Integer>> {
@Override
public int compare(Pair<Integer, Integer> p1, Pair<Integer, Integer> p2){
if(p1.getKey() != p2.getKey())
return p1.getKey() - p2.getKey();
return p1.getValue() - p2.getValue();
}
}
public List<Integer> topKFrequent(int[] nums, int k) {
if(k <= 0)
throw new IllegalArgumentException("k should be greater than 0");
HashMap<Integer, Integer> freq = new HashMap<Integer, Integer>();
for(int i = 0 ; i < nums.length ; i ++)
if(freq.containsKey(nums[i]))
freq.put(nums[i], freq.get(nums[i]) + 1);
else
freq.put(nums[i], 1);
if(k > freq.size())
throw new IllegalArgumentException("k should be less than the number of unique numbers in nums");
PriorityQueue<Pair<Integer, Integer>> pq = new PriorityQueue<Pair<Integer, Integer>>(new PairComparator());
for(Integer num: freq.keySet()){
int numFreq = freq.get(num);
if(pq.size() == k){
if(numFreq > pq.peek().getKey()){
pq.poll();
pq.add(new Pair(numFreq, num));
}
}
else
pq.add(new Pair(numFreq, num));
}
ArrayList<Integer> res = new ArrayList<Integer>();
while(!pq.isEmpty())
res.add(pq.poll().getValue());
return res;
}
}
