欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

从海量数值中找出最大的N个元素的算法实现

程序员文章站 2024-03-15 21:17:00
...

本例要求

  • 一个文件中存有海量(大小超过40W)Long类型数值,每个数值一行,且各不相同
  • 堆内存大小4M
  • 以最快方式找出海量数值中最大的前100个数值,限时2s以内

解题思路

首先,肯定不能将海量数据压入TreeSet中进行排序,这样会造成堆内存溢出。
首先想到的是,采用TreeSet,维护一个小顶堆,堆里只有k个元素,从而保证堆内存不溢出。然后将后面的元素压入堆中,基于TreeSet的排序功能排序后,poll掉最上面的一个元素(最小元素)。
其实JDK1.5以后还提供了PriorityQueue,如果海量数据里有重复数据,建议采用该优先级队列,因为TreeSet是不能存放重复数据的。

代码实现

public class FindTopN {
    /**
     * 从文件中找出最大的前N个数值
     *
     * @param filePath 文件路径
     * @param n
     * @return
     */
    public Long[] findTopN(String filePath, int n) throws IOException {
        File srcFile = new File(filePath);
        if (!srcFile.exists()) {
            throw new IllegalArgumentException("File not exist at filepath [" + filePath + "]");
        }
        //创建一个小顶堆的TreeSet
        TreeSet<Long> minHeap = new TreeSet<>();
        //按行读取文件内容
        LineIterator iterator = FileUtils.lineIterator(srcFile, "UTF-8");
        while (iterator.hasNext()) {
            String line = iterator.nextLine();
            if (StringUtils.isNotEmpty(line)) {
                Long number = Long.parseLong(line);
                minHeap.add(number);
                if (minHeap.size() > n) {
                    minHeap.pollFirst();
                }
            }
        }
        iterator.close();
        return minHeap.toArray(new Long[]{});
    }
}