利用有序队列寻找最大的K个数

简介:
    这是一个很常见的算法问题,从一组数中选出最大的K个。
《编程之美》上也有这个问题的一些解法。其中,一种较好的解法就是利用有序队列(如JAVA中的PriorityQueue),主要的算法思路如下:
先从第一个数开始,依次入队k个数,此时,有序队列以对这k个数排序完成,按照从小(队列首)到大(队列尾)顺序排列。
然后,依次遍历后面的剩余数字,当队列首小于即将入队的数时,出队,并将当前的数入队。如此重复,直到遍历完毕。
此时,队列中剩下的即是最大的K个数了。
具体范例如下,使用JAVA编写。
 
/** 
* @(#)Kmax.java 

* Kmax application 

* @author    
* @version 1.00 2010/2/19 
*/
 
import  static java.lang.System.out; 
import java.util.Comparator; 
import java.util.PriorityQueue; 

class MyComparator  implements Comparator { 
   public  int compare(Object a, Object b) { 
     return ((Long)a).compareTo((Long)b); 
  } 


public  class Kmax { 
         private  long []n; 
         private  int maxNum = 20; 
         private  int k = 5; 
         private  final  static  int BOUND = 1000; 
         
         private  void generateNumbers() { 
          n =  new  long[maxNum]; 
           for( int i = 0; i < maxNum; i++) { 
            n[i] = Math.round(Math.random() * BOUND); 
            out.println(n[i]); 
          } 
        } 

         private  void selectKmax() { 
          PriorityQueue pq =  new PriorityQueue(k,  new MyComparator()); 
           for( int i = 0; i < k; i++) { 
            pq.offer(n[i]); 
          } 
            
           for( int i = k; i < maxNum; i++) {    
             if(n[i] > (Long)pq.peek()) { 
              pq.poll(); 
              pq.offer(n[i]); 
            } 
          } 
            
          out.println( "-----------------------"); 
           while(pq.size() > 0) { 
            out.println((Long)pq.poll()); 
          } 
        } 
         
         public  static  void main(String[] args) { 
          Kmax kmax =  new Kmax(); 
          kmax.generateNumbers(); //产生maxNum个随机整数 
          kmax.selectKmax(); //从中选出k个最大的数,并输出 
          out.println( "Complete!"); 
        } 

 
这个算法速度较快,是一种极好的解法。









本文转自 kevx 51CTO博客,原文链接:http://blog.51cto.com/spinlock/277124,如需转载请自行联系原作者
目录
相关文章
|
9月前
|
算法 程序员 测试技术
【数据结构-队列 二】【单调队列】滑动窗口最大值
【数据结构-队列 二】【单调队列】滑动窗口最大值
86 0
|
算法 测试技术 C#
C++二分查找算法的应用:长度递增组的最大数目
C++二分查找算法的应用:长度递增组的最大数目
|
8月前
|
索引
队列的数组实现
队列的数组实现
29 0
|
8月前
|
存储 算法
数据结构和算法学习记录——特殊线性表之队列-队列的概念、队列结构体类型定义 、基本接口函数、初始化函数、销毁队列函数、入队列函数、判断队列是否为空、出队列函数、读取队头队尾的数据 、计算队列数据个数
数据结构和算法学习记录——特殊线性表之队列-队列的概念、队列结构体类型定义 、基本接口函数、初始化函数、销毁队列函数、入队列函数、判断队列是否为空、出队列函数、读取队头队尾的数据 、计算队列数据个数
57 0
|
消息中间件 前端开发 JavaScript
使用数组实现队列
使用数组实现队列
68 0
|
存储 索引
【数据结构】—— 队列(有序队列及环形队列的数组实现)
【数据结构】—— 队列(有序队列及环形队列的数组实现)
222 0
【数据结构】—— 队列(有序队列及环形队列的数组实现)
|
消息中间件 存储 缓存
基于数组和链表实现队列
创建大数组实现对象:里面包含的信息公共初始化: 初始化页工厂:索引页工厂、数据页工厂、元数据页工厂,初始化数组索引、初始化数据页索引,通过队列前置索引页工厂获取索引页,获取队列front索引buffer,获取front,也即索引。这个实现和kafka是类似的,也即需要有相关页信息 入队列:进行入队操作是一个追加的操作,首先判断容量是否够,不够,则进行扩容操作。通过缓存拿到映射页实现,然后通过映射页。再通过锁,仅锁定创建页,索引用完后进行移除操作,映射页面实现,使用双向校验,如果为空,则创建页索引对象,通过索引拿到文件名称,然后通过读写通道进行读写操作。使用fileChannal调用映射方法获取
154 0
基于数组和链表实现队列
队列的最大值(剑指offer59-II)
请定义一个队列并实现函数 max_value 得到队列里的最大值,要求函数max_value、push_back 和 pop_front 的均摊时间复杂度都是O(1)。 若队列为空,pop_front 和 max_value 需要返回 -1
145 0
|
C++
C++实现线性表 - 05 队列(数组实现)
今天我们来学习一下队列结构,这也是我们讲线性表的最后一个部分了,这里会分成两节来讲,先讲数组的实现,再讲链表的实现。由于双端队列是包含了单端队列的操作,所以我们这里为了讲的更全一些,代码实现为双端队列。
158 0
C++实现线性表 - 05 队列(数组实现)

热门文章

最新文章