Go语言视频零基础入门到精通

javalearner

这是一个很常见的算法问题，从一组数中选出最大的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 = Math.round(Math.random() * BOUND);
      
             out.println(n);
      
           }
      
         }
      

      
         
      private
      void selectKmax() {
      
           PriorityQueue pq =
      new PriorityQueue(k,
      new MyComparator());
      
           
      for(
      int i = 0; i < k; i++) {
      
             pq.offer(n);
      
           }
      
            
      
           
      for(
      int i = k; i < maxNum; i++) {   
      
            
      if(n > (Long)pq.peek()) {
      
               pq.poll();
      
               pq.offer(n);
      
             }
      
           }
      
            
      
           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!");
      
         }
      
}
      

      
     
   
      运行结果：
     

     
C:at>java
     
303
     
868
     
903
     
678
     
241
     
946
     
872
     
810
     
281
     
703
     
796
     
75
     
593
     
866
     
850
     
557
     
74
     
224
     
400
     
717
     
-------------
     
866
     
868
     
872
     
903
     
946
     
Complete!
     
   
     这个算法速度较快，是一种极好的解法。
     
    本文出自 “Kevx"s Blog” 博客，请务必保留此出处http://spinlock.blog.51cto.com/607469/277124
   
   

   
     
     
      
      

        
      

        
      
     
   

  


源码下载：http://file.javaxxz.com/2014/11/10/000223531.zip