347. 前 K 個高頻元素 - 力扣（LeetCode）

/**

? ? ? ? 桶排序:

? ? ? ? ? ? ? ? 首先遍歷數組,使用HashMap統計每個元素出現的次數

? ? ? ? ? ? ? ? 創建一個大小為length + 1的List數組,下標代表元素出現次數,出現次數一致的元素放在同一個數組中

? ? ? ? ? ? ? ? 倒數遍歷List數組即可得得到前K個高頻元素

? ? ? ? 細節注意:

? ? ? ? ? ? ? ? 長度為length的數組,可能存儲的元素全部相同,則最高頻元素出現次數為length

? ? ? ? ? ? ? ? 下標代表頻率即元素出現次數,則List數組大小需為length + 1

*/

class Solution {/**桶排序:首先遍歷數組,使用HashMap統計每個元素出現的次數創建一個大小為length + 1的List數組,下標代表元素出現次數,出現次數一致的元素放在同一個數組中倒數遍歷List數組即可得得到前K個高頻元素細節注意:長度為length的數組,可能存儲的元素全部相同,則最高頻元素出現次數為length下標代表頻率即元素出現次數,則List數組大小需為length + 1*/public int[] topKFrequent(int[] nums, int k) {//統計元素出現次數Map<Integer,Integer> countMap = new HashMap<>();for(int num : nums) {countMap.put(num,countMap.getOrDefault(num,0) + 1);}//創建List數組,按照出現次數,將元素存入List數組中List<Integer>[] buckets = new ArrayList[nums.length + 1];for(int num : countMap.keySet()) {//讀取當前num的頻率int freq = countMap.get(num); //將元素添加到對應的“頻率桶中”if(buckets[freq] == null) {buckets[freq] = new ArrayList<>();}buckets[freq].add(num);}//倒序遍歷頻率桶收集結果int[] result = new int[k];int index = 0; //result填充位置for(int i = buckets.length - 1; i >= 0 && index < k; i--) {if(buckets[i] != null) {for(int num : buckets[i]) {result[index] =  num;index++;if(index == k) {break;}}}}return result;}
}