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

原题是：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()));
	}
}

错别字横行，看着烦！

坑爹的错别字.看了半天.

要考你的是用大小堆求前N大，他要你写代码实现吗？

   不知道java里面那个是用大小堆实现的类，TreeSet是吗？
            

我觉得他有2个考点：
1、考你如何建堆   2、考你对java基础类库的理解

还是数据结构。。。

我觉得他要考你数据结构与算法，不是考你代码工人的！

http://tangkund3218-126-com.iteye.com/blog/1173449有人答过了

很基础吧...

import java.util.Arrays;
import java.util.Random;

public class Top {

	public static void main(String[] args) {
		int i = 0;
		int[] start = new int[10000];
		for ( i = 0; i < 10000; i++)
			start[i] = new Random().nextInt();
		int[] top = (int[]) start.clone();
		Arrays.sort(top);
		for(;i>9900;i--){
		System.out.println(top[i-1]);
		}
	}

}

public class Main {

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		
		//随机生成10000+数字
		int[] input = new int[100000];
		Random r = new Random();
		for(int i=0;i<input.length;++i){
			input[i] = Math.abs(r.nextInt(10000));
		}
		
		int[] result = topN(input,100);
		
		for(int j=0;j<result.length;++j){
			System.out.print(result[j]+" ");
		}
		
	}
	
	public static int[] topN(int[] input,int top){
		int[] result = new int[top];
		
		if(input.length <= top){
			for(int i=0;i<input.length;++i){
				result[i] = input[i];
			}
			Arrays.sort(result);
			return result;
		}
		
		for(int j=0;j<top;++j){
			result[j] = input[j];
		}
		Arrays.sort(result);
		
		outer:for(int k=top;k<input.length;++k){
			if(input[k] <= result[0]){
				continue;
			}
			
			int pointer = -1;
			int bigger = input[k];
			
			for(int m=0;m<top;++m){
				if(bigger == result[m]){
					continue outer;
				}else if(bigger > result[m]){
					pointer = m;
				}
			}
			
			//前移
			for(int n=0;n<pointer;++n){
				result[n] = result[n+1];
			}
			result[pointer] = bigger;
			
		}
		
		return result;
	}

}

粗写了一个。不知对否。