这是一个很常见的算法问题，从一组数中选出最大的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!");
}
}
* @(#)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，如需转载请自行联系原作者
