## 優先隊列 本質是二叉堆（Binary Heap）的結構，利用一個數組結構來實現完全二叉樹。  其中隊列的優先級是可以自定義的。 ### 特性 數組第一個元素array[0]優先級最高； 給定一個下標i，對于array[i]而言： * 父節點下標： (i-1)/2 * 左側節點下標：2*i + 1 * 右側節點下標：2*i + 2 ### LeetCode練手 347. 前 K 個高頻元素 ~~~ package com.mango.leet.code.middle; /** * 347. 前 K 個高頻元素 */ import java.util.*; /** * 給你一個整數數組 nums 和一個整數 k ，請你返回其中出現頻率前 k 高的元素。你可以按 任意順序 返回答案。 * * ? * * 示例 1: * * 輸入: nums = [1,1,1,2,2,3], k = 2 * 輸出: [1,2] * 示例 2: * * 輸入: nums = [1], k = 1 * 輸出: [1] * ? * * 提示： * * 1 <= nums.length <= 105 * k 的取值范圍是 [1, 數組中不相同的元素的個數] * 題目數據保證答案唯一，換句話說，數組中前 k 個高頻元素的集合是唯一的 * * 來源：力扣（LeetCode） * 鏈接：https://leetcode-cn.com/problems/top-k-frequent-elements * 著作權歸領扣網絡所有。商業轉載請聯系官方授權，非商業轉載請注明出處。 */ public class LC347 { public static void main(String[] args) { int[] nums = new int[]{1,1,2,2,3,3,3,3,3}; System.out.println(Arrays.toString(new Solution().topKFrequent(nums,2))); } static class Solution { public int[] topKFrequent(int[] nums, int k) { // 1. 先計算出數字出現的次數，放到countMap里 Map<Integer,Integer> countMap = new HashMap<>(); for(int i=0;i<nums.length;i++){ countMap.put(nums[i],countMap.getOrDefault(nums[i],0)+1); } // 2. 利用優先隊列，自定義優先級為數字出現的頻次 Queue<Integer> queue = new PriorityQueue(new Comparator() { @Override public int compare(Object o1, Object o2) { return countMap.get(o1) - countMap.get(o2); } }); countMap.forEach((int1,int2)->{ if(!queue.contains(int1)){ queue.offer(int1); } }); // 3. 取優先隊列的前k個數字返回 int[] result = new int[k]; for(int i=0;i<k;i++){ result[i] = queue.poll(); } return result; } } } /** * 2022-03-05 * 思路： * 1. 先計算出數字出現的次數，放到countMap里 * 2. 利用優先隊列，自定義優先級為數字出現的頻次 * 3. 取優先隊列的前k個數字返回 */ ~~~