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

最近有同事去腾讯面试,其中一个排序算法题:从1亿个数字中取出最大的100个. 我感觉用位图排序是比较合适的.位图排序的特点是用内存空间换取CPU时间.代码如下:

 

import java.util.Random;

 

public class Top100 {

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

 

int maxValue = Integer.MIN_VALUE;

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

if (maxValue < inputArray[i]) {

maxValue = inputArray[i];

}

}

byte[] bitmap = new byte[maxValue+1];

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

int value=inputArray[i];

bitmap[value] = 1;

}

 

int[] result = new int[100];

int index = 0;

for (int i = maxValue; i >= 0 & index < 100; --i) {

if (bitmap[i] == 1) {

result[index++] = i;

}

}

return result;

}

 

public static void main(String[] args) {

int numberCount = 90000000;

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);

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

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

}

}

}

 

我的机子是配置是CPU:Intel(R) Pentium(R) M processor 1.60GHZ,512M内存. 运行结果如下

1千万:1.297秒

2千万: 2.906秒

3千万:4.578秒

4千万:6.203秒

5千万:7.875秒

6千万:9.953秒

7千万:11.407秒

8千万:26.921秒

9千万:31.953秒

 

当运行到1亿数据时,机子几乎就没有反应了,这可能是物理内存已经耗尽,用虚拟内存了.

 

欢迎交流!

你把问题想复杂化了，单次循环，top100用红黑树，如果树大小小于100直接插入，否则比较树中最小值，大于则移去最小值，插入新值。

 

哈哈，最大堆正解，头100个节点不断构造就可以了

请问，用java实现，也就是一个treeset就可以了吗？

1.有负数么?
2.数重复么?

1.原理上讲就是一个长度为100的有序结构快速插入的问题.
2.不过放这么大的源数据,是否还有什么特别需要,是否有人知道?比如可以分成10个任务给10个CPU分别求top100,再合并之类的.

1亿的数据， 我建议用1亿的数据进行分割， 分割成10万*1000次；
10万条数据排序一次，取前最大的100条数据，放到缓存中，总共要进行1001次就可以了。
如果要考虑性能的问题， 我们可以用多线程进行排序。

import java.util.Random;
import java.util.Set;
import java.util.TreeSet;

public class TestSF {

public static Set<Integer> getTop100(int[] inputArray) {

TreeSet<Integer> top100 = new TreeSet();
for (int i = 0; i < inputArray.length; i++) {

if (top100.size()<100){
top100.add(inputArray[i]);
}else if ((Integer)top100.first()<inputArray[i]){
Object obj = top100.first();
top100.remove(obj);
top100.add(inputArray[i]);
}

}

return top100;

}

public static void main(String[] args) {

int numberCount = 100000000;

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();

Set<Integer> result = TestSF.getTop100(inputArray);

System.out.println("Spend time:"+(System.currentTimeMillis() - current));


}

}

我不太熟悉java，如果treeset是有序树的话，那就没问题