Java PriorityQueue如何访问队列内自定义对象成员?TopK高频元素实现
问题描述
假设我有如下整数数组:
[ 1,2,3,4,5,6,1,2,3,1,2... ]
我需要获取数组中出现频率最高的K个元素。提到“K个最高频元素”我第一时间想到了Max Heap(最大堆)数据结构,因此我决定创建自定义类,同时完成元素计数和优先级排序功能,类定义如下:
public class countedInts implements Comparable<countedInts>{ public int theInt, count; public countedInts(int a, int b) { this.theInt = a; this.count = b; } @Override public int compareTo(countedInts o) { return this.count - o.count; } }
该类本质是两个int类型值的配对结构,实现非常简单。
接下来是核心方法的初始实现代码:
public int[] topKFreq(int[] arr, int k) { PriorityQueue<countedInts> maxHeap = new PriorityQueue<>(Collections.reverseOrder()); for( int i=0; i<arr.length; i++ ) { // 若当前arr[i]还没有对应的countedInts计数对象 maxHeap.offer( new countedInts(arr[i], 1) ); // 若当前arr[i]已经存在对应的countedInts计数对象... countedInts tmp = maxHeap.get( ??? ); tmp.count++; maxHeap.offer( tmp ); } }
可以看到实现存在明显问题:遍历arr数组元素时,我需要检查maxHeap中是否已经存在对应记录当前arr[i]的countedInts对象,也就是需要访问PriorityQueue内部存储对象的成员变量。请问是否有方法可以实现该需求?或者针对这个问题是否存在更优的实现策略?
补充说明:该问题对应LeetCode平台的Top K Frequent Elements题目,我习惯在放弃思考查看官方题解前先自行探索实现方案,这种方式学习效果更好。
可行实现参考
有用户提供了如下可正常运行的实现策略,经过验证有效,发布在这里供其他开发者参考:
public class countedInts implements Comparable<countedInts>{ public int theInt, count; public countedInts(int a, int b) { this.theInt = a; this.count = b; } @Override public int compareTo(countedInts o) { return this.count - o.count; } } public int[] topKFrequent(int[] arr, int k) { // 边界情况处理 if( arr == null ) { return null; } else if( arr.length == 0 ) { return arr; } int[] ret = new int[k]; HashMap<Integer,Integer> myMap = new HashMap<>(); PriorityQueue<countedInts> maxHeap = new PriorityQueue<>(Collections.reverseOrder()); // 填充HashMap完成元素频次统计 for( int i=0; i<arr.length; i++ ) { if( !myMap.containsKey(arr[i]) ) { myMap.put(arr[i], 1); } else { myMap.put(arr[i], myMap.get(arr[i])+1); } } // 将统计完成的频次数据存入最大堆 for( Map.Entry<Integer, Integer> glork : myMap.entrySet() ) { maxHeap.offer( new countedInts(glork.getKey(), glork.getValue()) ); } // 取出频率最高的K个元素 for( int i=0; i<k; i++ ) { countedInts tmp = maxHeap.poll(); ret[i] = tmp.theInt; } return ret; }
内容的提问来源于stack exchange,提问作者Pete
相关产品推荐
相关产品推荐

