一道腾讯面试题:从大量数字中取出 top 100

构造100大的数组A，循环放其他的数字。
数组A越来越接近最后要的100个大数，所以后面的插进来的数字小于数组最小值的概略最大，大于数组最大值的概略最小。这样倒着往上比较，插入到合适的位置，然后删除最小值。

纯属理论分析。也许最小顶堆最靠谱！
------------------------------------------
说一下楼主的方法，实际上是基数排序的变种，所需空间取决于给定数字中的最大值，如果遇见一个long型的大数字估计就死了。还有楼主没有统计重复数字。

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

public class Top100 {
private static Node head = null;
private static Node end = null;
private static Node tempNode = null;
private static Node node = null;

public static int[] getTop100(int[] inputArray) {

int result[] = new int[100];
int k = 100;
if (inputArray.length < 100) {
k = inputArray.length;
}
for (int i = 0; i < 100; ++i) {
result[i] = inputArray[i];
}

Arrays.sort(result);

for (int i = k - 1; i >= 0; i--) {
node = new Node(result[i], tempNode);
if (i == k - 1) {
head = node;
} else {
tempNode.right = node;
}
if (i == 0) {
end = node;
}else{
tempNode = node;
}
}
tempNode = end ;


for (int i = 100; i < inputArray.length; i++) {
int tempValue = inputArray[i];
if (tempValue <= end.value) {
continue;
}else{
tempNode = end;
setValue(inputArray[i]) ;
}
}

for (int i = 0; i < 100; i++) {
if (i == 0) {
node = head;
} else {
node = node.right;
}
result[i] = node.value;
}

return result;

}

private static void setValue(int tempValue) {
if (tempNode.value < tempValue) {
tempNode = tempNode.left;
//最大的
if(tempNode==null){
node = new Node(head,tempValue );
head.left = node ;
head = node ;
removeEnd() ;
}else{
setValue(tempValue);
}
} else if (tempNode.value != tempValue) {
node = new Node(tempValue, tempNode);
//要替代end
if(tempNode.right==end){
end.left.right = node ;
end = node ;
}else{
try {
tempNode.right.left = node;
} catch (Exception e) {
// TODO Auto-generated catch block
System.err.println(tempNode.right) ;
e.printStackTrace() ;
System.exit(0) ;
}
tempNode.right = node;
removeEnd() ;
}
}
}

private static void removeEnd(){
end = end.left ;
end.right = null ;
}

public static void main(String[] args) {

int numberCount = 1000000;

int maxNumber = numberCount;

int inputArray[] = new int[numberCount];

Random random = new Random();

for (int i = 0; i < numberCount; ++i) {

inputArray[i] = Math.abs(random.nextInt(maxNumber));

}

System.out.println("Sort begin...");

long current = System.currentTimeMillis();

int[] result = Top100.getTop100(inputArray);

System.out.println(System.currentTimeMillis() - current + "ms");

for (int i = 0; i < result.length; ++i) {

System.out.print(i + "." + result[i] + ",");

}

}

}

class Node {
protected int value;
protected Node left;
protected Node right;

public Node(int value) {
this.value = value;
}

public Node(int value, Node left) {
this.value = value;
this.left = left;
}

public Node(Node right, int value) {
this.right = right;
this.value = value;
}
}

楼上的代码有问题

应该用MapReduce的方式来更好吧

TreeSet<Integer> set = new TreeSet<Integer>();
List<Integer> lst = new ArrayList<Integer>();
int numberCount = 1000000000;
int maxNumber = numberCount;
Random random = new Random();
for (int i = 0; i < numberCount; i++) {
int randomInt = random.nextInt(maxNumber);
Integer inte = new Integer(randomInt);
if (set.contains(inte))
{
lst.add(inte);
}
if (set.size() < 100)
{
set.add(inte);
}
else
{
if (set.first().intValue() < randomInt)
{
set.remove(set.first());
set.add(randomInt);
}
}
}

Iterator iterator = set.iterator();
while(iterator.hasNext()) {
lst.add((Integer)iterator.next());
}

Collections.sort(lst);
for (int i = 0; i < 100; i++)
{
System.out.println(i + ":" + lst.get(lst.size() - i - 1));
}

这段代码貌似十几秒就可以了，每1KW用时不到2S。

编程之美上的一道题目

int max = 100000000;
BitSet bset = new BitSet(max);
Random random = new Random(); 
for(int i=0;i<max;i++){
bset.set(Math.abs(random.nextInt(max)));
}
System.out.println("加载完毕!");
long lo = System.currentTimeMillis();
int[] top100 = new int[100];
int location = 0;
for(int i=0;i<max;i++){
boolean bool = bset.get(i);
if(location==100){
break;
}
if(bool){
top100[location] = i;
location++;
}
}
System.out.println("花费:"+(System.currentTimeMillis()-lo));
for(int i=0;i<100;i++){
System.out.println(top100[i]);
}
花费:0

int max = 100000000;
BitSet bset = new BitSet(max);
Random random = new Random(); 
for(int i=0;i<max;i++){
bset.set(Math.abs(random.nextInt(max)));
}
System.out.println("加载完毕!");
long lo = System.currentTimeMillis();
int[] top100 = new int[100];
int location = 0;
for(int i=max;i>=0;i--){
boolean bool = bset.get(i);
if(location==100){
break;
}
if(bool){
top100[location] = i;
location++;
}
}
System.out.println("花费:"+(System.currentTimeMillis()-lo));
for(int i=0;i<100;i++){
System.out.println(top100[i]);
}
这样才对。

路过一次看看而已

public class findValue {
	
	public static void main(String[] args){
			
		int max = 10000*10000;
		int length=100;
		int ints[] = new int[max];
		Random random = new Random();
		for (int i=0;i<max;i++) {
			ints[i]=Math.abs(random.nextInt(max));
		}
		List<Integer> list = new ArrayList();

		long start = System.currentTimeMillis();
		int size=0;
		int value=0;
		list.add(ints[0]);
		for(int i=1;i<max;i++){
			value=ints[i];
			size=list.size();
			if(value<list.get(size-1)){
				if(size<length){
					list.add(value);
				}
				continue;
			}else if(value>list.get(0)){
				list.add(0,value);
				if(size==length){
					list.remove(size);
				}
				continue;
			}
			
			for(int j=0;j<size;j++){
				if(value>list.get(j)){
                                              //如果不需要排除重复数字，则去掉该判断
					if(j>0&&value!=list.get(j-1)){
						list.add(j,value);
						if(size==length){
						  list.remove(size);
						}
					}
					break;
				}
			 }
		}
		
		System.out.println("time:"+(System.currentTimeMillis()-start));
		
		System.out.println(list);
		TreeSet<Integer> set = new TreeSet();
		set.addAll(list);
		
		System.out.println(set.size()+":"+list.size());
		if(set.size()!=list.size()){
			System.out.println("error");
		}
		int i=0;
		for(Iterator<Integer> it=set.iterator();it.hasNext();){
			value=it.next();
			System.out.println(value+":"+list.get(list.size()-1-i));
			if(value!=list.get(list.size()-1-i)){
				System.out.println("error");
				break;
			}
			i++;
		}
	}
}

E2160 3G
time:2453