`
lc87624
  • 浏览: 143959 次
  • 性别: Icon_minigender_1
  • 来自: 北京
社区版块
存档分类
最新评论

简单地用Java解决topN问题

    博客分类:
  • java
阅读更多
个人blog原文地址http://www.gemoji.me/java_top_n/

距离上次写博客有一个月了, 反省下。今天先写篇简单点的,算是热热身吧。

写在前面
我想几乎每个找过工作的程序员都曾经在面试的时候遇到过如何求topN的问题,而且多数都能不假思索的回答:求topN大用小顶堆,求topN小用大顶堆(觉得反了的同学请去面壁。。。),但是应该也有一部分同学和我之前一样,一直只是把它作为一道面试题而已。

思路
说来不怕丢人,我真的是最近才遇到需要求top N大的场景,囧。。。当时的第一反应是要自己实现一个固定大小的二叉堆,因为印象中常用的Java工具类里并没有现成的实现,但是从头开始实现一个基础工具类是件挺麻烦的事情,别的不说,单是测试就得耗费不少功夫,网上虽然有很多现有实现,但是都不见得那么靠谱。于是想了一个折中的办法就是,对现有的成熟的Java工具类做封装,以达到想要的功能。

代码实现
JDK里有一个现成的工具类叫PriorityQueue,顾名思义,实现的是优先队列的功能,它能够保证每次插入新元素后,队列首位始终是优先级最高的元素,这正是我们想要的,但是它并没有对队列的容量做限制,因此只要对这一点做些许改造,就能达到我们期望的效果。代码如下:

	//固定容量的优先队列,模拟大顶堆,用于解决求topN小的问题
	public static class FixSizedPriorityQueue>{
		private PriorityQueue queue;
		private int  maxSize; //堆的最大容量

		public FixSizedPriorityQueue(int maxSize){
			if(maxSize <= 0) throw new IllegalArgumentException();			
			this.maxSize = maxSize;
			this.queue = new PriorityQueue(maxSize, new Comparator() {

				@Override
				public int compare(E o1, E o2) {
					return o2.compareTo(o1);
				}
			});
		}

		public void add(E e){
			if(queue.size() < maxSize){ //未达到最大容量,直接添加
				queue.add(e);
			}else{ //队列已满
				E peek = queue.peek();
				if(e.compareTo(peek) < 0){ //将新元素与当前堆顶元素比较,保留较小的元素
					queue.poll();
					queue.add(e);
				}
			}
		}

		public List sortedList(){
			List list = new ArrayList(queue);
			Collections.sort(list); //PriorityQueue本身的遍历是无序的,最终需要对队列中的元素进行排序
			return list;
		}

	}



注意一下构造PriorityQueue时用到的Comparator,这里面有个比较tricky的地方,因为代码本身是想实现一个大顶堆来解决求topN小的问题,而PriorityQueue的优先级定义是元素越小优先级越高,这与我们的期望相反,因此我们需要自定义PriorityQueue的Comparator,反转元素大小的定义,这样就能保证队列首位的元素是当前队列中最大的。而在比较新元素和队列首位元素的大小时,则是按照正常的元素大小定义做比较。

结尾
在需要快速实现需求的时候,我们可能没有足够的时间把代码写得很完美,如何写最少的代码实现想要的功能,也是我们日常工作中需要考虑的问题。
PS:文中若有纰漏之处,敬请拍砖。
分享到:
评论
2 楼 lc87624 2013-08-12  
luxury_zh 写道
最后一点不明白,为什么每次还要对队列进行排序,循环N次,调用poll方法每次取得都是当前队列最大的数字了。

你说的方法也是可以的,我当时应该是想保留queue里的数据,所以做了一份copy。
1 楼 luxury_zh 2013-08-04  
最后一点不明白,为什么每次还要对队列进行排序,循环N次,调用poll方法每次取得都是当前队列最大的数字了。

相关推荐

    寻找最优的topn算法

    在处理大量数据时,经常需要解决TopN问题,即根据某个可排序的属性(通常是数值型),从数据集中找出最大的前N个记录。尽管这个问题相对简单,但要设计出高效的算法并不容易。本文将对几种常见的TopN算法进行分析...

    topK 问题的5种解决方案

    ### TopK 问题的五种解决方案 在计算机科学与数据处理领域中,TopK 问题是一种常见的需求...希望以上内容能帮助读者更好地理解和掌握 TopK 问题的解决方案。如果有任何疑问或需要进一步解释的地方,请随时联系作者。

    Java实现n阶螺旋方阵

    在Java中实现n阶螺旋方阵是一项常见的编程任务,这有助于理解和掌握数组的操作以及循环控制结构的使用。下面我们将深入探讨如何用Java来实现这个功能。 首先,我们需要了解螺旋矩阵的基本概念。假设我们有一个n阶的...

    动态规划通用算法的java实现

    总之,动态规划是解决复杂问题的强大工具,通过Java实现,我们可以更直观地理解其背后的逻辑和效率。这个jar包提供了动态规划算法的实际应用,对于学习和提升编程技能非常有价值。通过阅读和分析源码,开发者可以...

    一个简单的top-k实现

    因此,它是解决Top-K问题的理想选择。 以下是一个基本的Java Top-K算法实现思路: 1. 初始化一个大小为K的优先队列,设置队列的比较器以降序排列元素。 2. 遍历输入数据集,对于每个元素,如果队列的大小小于K,则...

    查找ip代码

    例如,以下是一个简单的Java代码片段,展示了如何使用堆来解决TopN问题: ```java import java.util.PriorityQueue; public class TopNProblem { public List&lt;Integer&gt; topN(int[] nums, int N) { PriorityQueue...

    Java_EE技术面试常见问题.doc

    Java EE技术面试常见问题主要涵盖了数据结构、算法、设计模式以及Java基础等多个方面,这些都是面试者需要深入理解和熟练掌握的核心技能。以下是对这些知识点的详细解释: 1. **数据结构**: - **链表**:链表是一...

    Nutch使用入门

    3. **执行crawl命令** - 示例命令:`bin/nutch crawl urls -dir javaeye -depth 3 -topN 100 -threads 3`。参数含义分别为:抓取结果目录、抓取深度、每层抓取的URL数量、下载线程数。 **搜索功能:** 1. **部署...

    Java版数据结构与算法视频教程地址.txt

    通过以上知识点的学习,可以全面理解Java中常用的数据结构与算法,并能在实际开发工作中灵活运用这些工具解决复杂问题。掌握这些核心概念和技术不仅能帮助开发者更好地应对日常编码挑战,还能有效提升个人的技术竞争...

    Java数据结构和算法.pdf

    ### Java数据结构和算法知识点详解 #### 一、数组与简单排序 **数组**是Java中最基础...以上是对Java数据结构和算法的概述,每种数据结构和算法都有其特定的应用场景和优缺点,掌握它们是理解和解决实际问题的关键。

    java排序算法

    基本思想是将大问题分解成小问题来解决,最后再合并这些小问题的解得到大问题的解。自顶向下版本的合并排序首先将大数组分成两半,然后分别对两个子数组进行排序,最后将两个有序子数组合并成一个有序数组。这个过程...

    java数据结构和算法学习之汉诺塔示例

    Java中的汉诺塔示例展示了如何使用递归方法解决这个问题。以下是对给定代码的详细解释: 1. `doTowers` 方法是汉诺塔问题的核心,它接受三个参数:`topN` 表示圆盘的数量,`from` 和 `to` 分别表示起始柱子和目标...

    杭州新利软件集团 java笔试题

    - **基于Java**:Servlet是用Java编写的,可以利用Java的强大功能和生态系统。 - **服务器端执行**:Servlet运行在服务器端,能够访问服务器资源和环境。 - **可扩展性**:Servlet可以通过简单的配置进行扩展和修改...

    java数据结构与算法

    - 使用分治法可以在线性时间内解决问题。 #### 六、树 **6.1 树的定义及基本术语** - **树的定义** - 树是一种非线性的数据结构,它由节点组成。 - 树中的节点通过边相连。 - **基本术语** - 根节点(root)、...

    interview-algorithms-java:面试准备的算法问题,java版本

    在准备Java面试时,算法是不可或缺的一部分,因为它们是衡量编程技能、逻辑思维以及问题解决能力的关键指标。"interview-algorithms-java"项目是专为Java开发者设计的,旨在帮助他们应对面试中的算法挑战。该项目...

    JAVA如何调用Shell脚本

    本文主要介绍了JAVA如何调用Shell脚本,提供了一种实用的解决方案,即使用JAVA的Runtime.getRuntime().exec()方法调用Shell脚本。下面将详细介绍该方法的实现过程和注意事项。 为什么需要调用Shell脚本 在实际项目...

    2021字节跳动面试参考手册.pdf

    - 解决矩形覆盖问题通常使用递归和动态规划方法。 7. 调整数组顺序使奇数位于偶数前面。 - 通过双指针方法可以在O(n)时间内完成调整。 8. 数组中出现次数超过一半的数字。 - 可以使用Boyer-Moore投票算法在O(n)...

    java经典笔试题

    - **注意**:递归算法在较大的 `n` 值下可能会导致性能问题或栈溢出。 #### 十、程序设计题解析 - **题目描述**:要求实现一个简单的事件驱动模型,模拟猫叫后老鼠逃跑、主人惊醒的场景。 - **解决方案**(C#语言...

    2011海南省java版本入门.docx

    解决约瑟夫环问题,即编号为 1 到 n 的 n 个人按顺时针方向围坐成一圈,从第 s 个人开始按顺时针方向报数,数到第 m 个人出列,然后从出列的下一个人重新开始报数,直到所有人出列为止。 #### 实现思路 1. **创建...

Global site tag (gtag.js) - Google Analytics