力扣-347.前K个高频元素

题目描述

给你一个整数数组 nums 和一个整数 k ，请你返回其中出现频率前 k 高的元素。你可以按 任意顺序 返回答案。

提示：题目数据保证答案唯一，换句话说，数组中前 k 个高频元素的集合是唯一的

进阶：你所设计算法的时间复杂度 必须 优于 O(n log n) ，其中 n 是数组大小。

class Solution { public int[] topKFrequent(int[] nums, int k) { Map<Integer,Integer> map = new HashMap<>();// for (int i = 0; i < nums.length; i++) { map.put(nums[i], map.getOrDefault(nums[i],0)+1); } PriorityQueue<Integer> pq = new PriorityQueue<>(new Comparator<Integer>() { @Override public int compare(Integer o1, Integer o2) { return map.get(o2) - map.get(o1); } });//存值，自定义排序规则 Set<Integer> set = map.keySet(); for (Integer key: set){ pq.add(key); } int[] res = new int[k]; for (int i = 0; i < k; i++) { res[i] = pq.poll(); } return res; }}

小结：题目思路比较简单，难点在于优先级队列的使用和Map的遍历。

优先级队列PriorityQueue

// 自然排序（升序）PriorityQueue<Integer> pq1 = new PriorityQueue<>();pq1.add(3); pq1.add(1); pq1.add(2); // 实际存储顺序可能无序，但poll()返回最小值并删除，peek()返回最小值// 自定义降序排序 Lambda表达式PriorityQueue<Integer> pq2 = new PriorityQueue<>((a, b) -> b - a);pq2.add(3); pq2.add(1); pq2.poll(); // 返回3// 自定义排序规则PriorityQueue<Node> queue = new PriorityQueue<>(new Comparator<Node>() { @Override public int compare(Node n1, Node n2) { // 按 priority 升序 return n1.priority - n2.priority; }});

Map的遍历方法

// 键找值Set<Integer> keys = map.keySet();for (Integer key : keys) { System.out.println(key + map.get(key));}// 键值对Set<Map.Entry<Integer, String>> sets = map.entrySet(); //将键值对封装为Entry类型for (Map.Entry<Integer, String> set : sets) { System.out.println(set.getKey()); System.out.println(set.getValue());}// Lambda表达式map.forEach((k, v) -> System.out.println(k + v));