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

hikelee

浏览: 8058 次
性别:
来自: 深圳

最近访客更多访客>>

luliangy

博主相关

博客

微博

相册

留言

关于我

文章分类

全部博客 (3)

社区版块

存档分类

腾讯面试算法 QQ J#

最近有同事去腾讯面试,其中一个排序算法题:从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亿数据时,机子几乎就没有反应了,这可能是物理内存已经耗尽,用虚拟内存了.

欢迎交流!

分享到：

算法,从已知数列中找出n个数,使其相加和 ... | Portlet标准:JSR168/JSR286/WSRP

2010-03-30 22:56
浏览 4113
评论(99)
论坛回复 / 浏览 (98 / 65909)
分类:编程语言
查看更多

99 楼 liuxuejin 2011-03-17

paohui01 写道

taojingrui 写道

这样的考题，我遇过多次了。其实这类题，考官考的东西并不完全是算法。完全追求算法，就陷进去了。考题考的是两方面，一是考虑内存，纯粹用排序算法是不可能的，光int[] nums = new int[100000000];这一句就可能导致内存不够。（增加内存根本不是考官希望的，这么个小程序就要增加内存？）二是考虑在内存许可的情况下，尽量提高速度。

方法1
基本上，这道题如果不考虑数据录入，调用两次循环，上亿的数字中找top100，用不到1秒应该就够了。
提示：
1.考虑用位（bit）数组，1亿bit需要多少内存？100000000/1024/1024/8<12M，就是10亿数字，也不到120M
2.一个bit的数组大小为1亿，bit[i]=0,表示i数据不存在，bit[i]＝1，表示i数据存在。（循环1次1亿数据，不用比较数据大小）
3.最后找到bit数组中，bit[i]＝1且top100 i（循环1次）

方法2
建立一张数据库表，把上亿数据录入数据库，有索引的情况下，在上亿数据中找top100，也是很快的（不考虑数据录入数据库的时间）

int[] nums = new int[100000000];
内存溢出拉？
java int占32位相当于4个字节
1亿个int占4亿个字节....
4亿个字节差不多相当于380M 能溢出？1G的内存就够用

第一种方法看不懂

使用TreeSet感觉是最好解决方法拉(参考skzr.org的代码)
如果觉得内存会不够用的话
数据放到文件里面读取好拉
内存永远不会溢出

4亿个字节只有380M！求怎么算的？

98 楼 liuxuejin 2011-03-17

taojingrui 写道

我想问问，你的bit数组在java是如何构建的？

97 楼 jeho0815 2011-03-16

import java.util.ArrayList;
import java.util.List;
import java.util.Random;

public class GetTop100 {

private static List<Integer> result = new ArrayList<Integer>();
/**
* @param args
*/
public static void main(String[] args) {
int count = 100000000; //要处理的数据量
int maxNumber = count;
int inputArray[] = new int[count];
Random random = new Random();
for (int i = 0; i < count; ++i) {
inputArray[i] = Math.abs(random.nextInt(maxNumber)); //随机生成的数组
}

System.out.println("Sort begin...");
long current = System.currentTimeMillis();
getTop100(inputArray);
System.out.println(System.currentTimeMillis() - current + " result:"+result.size());
for (int i = 0; i < result.size(); ++i) {
System.out.print(result.get(i) + ",");
}
}

private static void getTop100(int[] inputArray) { //得到前100的数据
for(int i = 0 ; i < inputArray.length ; i ++){
if(i < 100){
add(inputArray[i]);//前100个位自动插入
}else if(inputArray[i] > result.get(0)){
insert(inputArray[i]);//后面的为先删除再插入
}
}
}

private static void insert(int value) {
result.remove(0);//删除第一个
int index = result.size();//以下同添加
if(value > result.get(index-1)){
result.add(value);
}else{
for(int i = 0 ; i < index ; i++){
if(value <= result.get(i)) {
result.add(i, value);
return;
}
}
}
}

private static void add(int value) {
int index = result.size();
if(result.size() == 0){
result.add(value); //当为第一个时直接添加
}else if(value > result.get(index-1)){
result.add(value); //当为最后一个，就是最大的时候，也直接添加
}else{ //在lsit中间，则要遍历查找要出入的地方
for(int i = 0 ; i < index ; i++){
if(value <= result.get(i)) {
result.add(i, value);
return;
}
}
}

}

}
重新写的一个，解决了重复数据的问题。并且时间为两秒多一点点！

96 楼沙舟狼客 2011-03-16

这题对于我初学者来说有点难度！！！

95 楼 jeho0815 2011-03-16

楼主的排序时错误的。。。重复数据竟然没算

94 楼 chenyongxin 2010-12-09

luke_kai 写道

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

}

}

如果有重复数据怎么办？

93 楼 pengmj 2010-12-09

luke_kai 写道

不可能吧，我写的那段程序，亿级的数据花销 2.3秒
Spend time:2375

数组值都是0，当然是这样咯。

92 楼 sunnyfun 2010-12-07

题目有漏洞吧，这么大数据量数据源是什么？放内存？不可能吧，迟早会溢出的，一般用外排序，搞个B-tree什么的，翻翻数据结构的书就是了

91 楼请输入用户名 2010-12-06

luke_kai 写道

速度果然很快
1千万数据
Sort begin...
Spend time:266
不过再多的话我电脑就抛异常了，想来是内存不够了。。
java.lang.OutOfMemoryError: Java heap space

90 楼 fairplay 2010-05-29

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

89 楼 qyhdt 2010-05-29

路过一次看看而已

88 楼 lzj0470 2010-05-28

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]);
}
这样才对。

87 楼 lzj0470 2010-05-28

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

86 楼 Curapica 2010-04-10

编程之美上的一道题目

85 楼 millton 2010-04-07

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。

84 楼 colorless 2010-04-07

应该用MapReduce的方式来更好吧

83 楼 willamsccd 2010-04-07

楼上的代码有问题

82 楼 ansjsun 2010-04-02

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

81 楼 chunquedong 2010-04-02

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

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

80 楼 pclfs1983 2010-04-02

Exception in thread "main" java.lang.OutOfMemoryError: Java heap space
at Top100.main(Top100.java:62)

楼主的程序好像没有经过测试的

« 上一页 1 2 3 4 5 下一页 »

发表评论

您还没有登录,请您登录后再发表评论

最近访客更多访客>>

博主相关

文章分类

社区版块

存档分类

最新评论