?LeetCode刷題實戰(zhàn)347：前 K 個高頻元素
Given an integer array nums and an integer k, return the k most frequent elements. You may return the answer in any order.
示例
示例 1:
輸入: nums = [1,1,1,2,2,3], k = 2
輸出: [1,2]
示例 2:
輸入: nums = [1], k = 1
輸出: [1]
解題
class Solution {
public int[] topKFrequent(int[] nums, int k) {
//將每個數(shù)字的出現(xiàn)次數(shù)放入HashMap
Map<Integer, Integer> counts = new HashMap<>();
for(int i = 0; i < nums.length; i++){
if(counts.containsKey(nums[i])){
counts.put(nums[i], counts.get(nums[i])+1);
} else {
counts.put(nums[i], 1);
}
}
//建立只有k個元素的最小堆
PriorityQueue<Integer> minHeap = new PriorityQueue<>(new Comparator<Integer>(){
@Override
public int compare (Integer a, Integer b){
//要重寫compare函數(shù)：最小堆中存的是數(shù)字，但比較的是數(shù)字出現(xiàn)的頻率。默認是大頂堆。
return counts.get(a) - counts.get(b);
}
});
for(Integer key: counts.keySet()){
if(minHeap.size() < k) {
minHeap.add(key);
} else {
if(counts.get(key) > counts.get(minHeap.peek())){
minHeap.remove();
minHeap.add(key);
}
}
}
//輸出結果
int[] result = new int[k];
for(int i = 0; i < result.length; i++){
result[i] = minHeap.remove();
}
return result;
}
}