看网友的一道腾讯面试题有感

原题是：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>() {
			@Override
			public 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 算法，其实就是构建小根堆