You need to enable JavaScript to run this app.
优惠活动
大模型
产品
解决方案
定价
更多

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

相关产品推荐
方舟 Agent Plan

超全模态模型 × Harness 升级,最新支持 Deepseek-V4.1-Flash、GLM-5.3 系列、Doubao-Seedream-5.0-pro、Kimi-K3 (部分), 限时 9.9 元起

最近更新时间:2026.08.30 20:36:33