目录
LeetCode之路——347. 前 K 个高频元素
分析
优先队列
简单示例
运行结果
源码简析
LeetCode之路——347. 前 K 个高频元素
给你一个整数数组 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个高频元素的集合是唯一的
进阶：你所设计算法的时间复杂度 必须 优于 O(n log n) ，其中 n 是数组大小。
分析
1.需要统计各个元素的频率，用Map，元素为key，频率为value。
2.通过map排序(从大到小)选出k个元素。
3.推荐优先队列
class Solution {public int[] topKFrequent(int[] nums, int k) {// 优先队列默认排序：小的在队首queue[0]=minPriorityQueue<int[]> pq = new PriorityQueue<>((o1, o2) -> o1[1] - o2[1]);int[] res = new int[k]; // 答案数组为 k 个元素Map<Integer, Integer> map = new HashMap<>(); // 记录元素出现次数for(int num : nums) map.put(num, map.getOrDefault(num, 0) + 1);for(var x : map.entrySet()) { // entrySet 获取 k-v Set 集合// 将 kv 转化成数组int[] tmp = new int[2];tmp[0] = x.getKey();tmp[1] = x.getValue();pq.offer(tmp);if(pq.size() > k) {pq.poll();}}for(int i = 0; i < k; i ++) {res[i] = pq.poll()[0]; // 获取优先队列里的元素}return res;}
}
-
时间复杂度：O(n logk)
-
空间复杂度：O(n)
优先队列
优先级队列（PriorityQueue）是一种特殊类型的队列，它根据元素的优先级进行排序，使得可以以优先级最高的元素首先出队。优先级队列通常用最小堆（Min-Heap）数据结构实现，但也可以用最大堆（Max-Heap）来实现，具体取决于所需的排序顺序。
Java中优先级队列的主要特点和用法：
-
元素排序： 优先级队列中的元素根据其优先级进行排序，通常具有特定的比较规则或者通过元素的自然顺序来排序。
-
最小堆和最大堆： 默认情况下，Java的优先级队列是最小堆，即具有最小优先级的元素首先出队。可以通过提供自定义比较器来实现最大堆，以便具有最大优先级的元素首先出队。
-
插入和删除： 优先级队列支持插入和删除元素的操作，插入操作通常称为
offer()或add()，删除操作通常称为poll()。 -
获取元素： 优先级队列允许查看队列中的优先级最高的元素而不移除它，这通常使用
peek()方法。 -
元素不重复： 默认情况下，Java中的优先级队列不允许重复元素，每个元素在队列中只出现一次。如果需要允许重复元素，可以自行实现。
简单示例
此示例创建了一个最小堆的优先级队列，插入一些元素，并演示了如何查看和删除队列中的元素：
public class PriorityQueueExample{public static void main(String[] args) {// 创建一个最小堆的优先级队列PriorityQueue<Integer> minHeap = new PriorityQueue<>();
for (int i = 0; i < 5; i++) {int num =new Random().nextInt(100);System.out.println("随机数："+ num);minHeap.offer(num); // 查看队列中的最小元素int minElement = minHeap.peek();System.out.println("最小元素: " + minElement);}
// 删除队列中的最小元素int removedElement = minHeap.poll();System.out.println("删除的元素: " + removedElement);}
}
运行结果
源码简析
offer(E e)默认实现了最小堆的排序。也就是queue[0]=min的效果
public boolean offer(E e) {if (e == null)throw new NullPointerException();modCount++;int i = size;if (i >= queue.length)grow(i + 1);size = i + 1;if (i == 0)queue[0] = e;elsesiftUp(i, e);return true;}
// 在位置k插入x，通过比较将x放到最顶端private void siftUp(int k, E x) {if (comparator != null)siftUpUsingComparator(k, x);elsesiftUpComparable(k, x);}
