从海量数值中找出最大的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[]{});
}
}
推荐阅读
-
从海量数值中找出最大的N个元素的算法实现
-
找出具有n个元素的集合中最大的两个元素,要求比较次数尽可能少(三种算法的思考)
-
设计一个算法:用不多于3n/2的平均比较次数,在数组A[1,...,n]中找出最大值和最小值的元素
-
设计一个最优算法来查找一n个元素数组中的最大值和最小值
-
Python cookbook(数据结构与算法)找到最大或最小的N个元素实现方法示例
-
算法设计与分析(第一篇)(分治与递归)(二分查找)在n+logn-2次比较中找出a[n]的最大元素与次大元素
-
Python cookbook(数据结构与算法)找到最大或最小的N个元素实现方法示例
-
通过PHP从指定范围内的两个正整数值中找出最大值
-
通过PHP从指定范围内的两个正整数值中找出最大值