看网友的一道腾讯面试题有感
原题是：10000+个数字钟找出top100
我稍作改动，可以是top任何数字。
package model.test;import java.util.Arrays;import java.util.Comparator;import java.util.HashSet;import java.util.Random;import java.util.Set;import java.util.TreeSet;//10000+个数字钟找出top100 public class Top {Set<Integer> top;int topNumber;public Top(int topNumber,Set<Integer> inputValues) {this.topNumber = topNumber;this.top = new TreeSet<Integer>(new Comparator<Integer>() {@Overridepublic int compare(Integer o1, Integer o2) {return o1 - o2;}});for(int input:inputValues){this.add(input);}}public Integer[] getTop(){return this.top.toArray(new Integer[] {});}private void add(int value) {if (this.topNumber == this.top.size() && value > (Integer) this.top.toArray()[0]) {this.top.remove(this.top.toArray()[0]);}if (this.top.size() < this.topNumber) {this.top.add(new Integer(value));}}public static void main(String[] args) {//准备测试数据Set<Integer> input=new HashSet<Integer>();for(int i=0;i<50000;i++){input.add(new Integer(new Random().nextInt(Integer.MAX_VALUE)));}//输出结果System.out.println(Arrays.toString(new Top(1000, input).getTop()));}} 1 楼 michaelh0226 2011-10-21 这个是百度面试题里面的TopK 算法，其实就是构建小根堆