l********y 发帖数: 1327 | 1 有一个int array,10000个元素,里面放有数字0到100,但是缺少某一个数字,问怎么
样最优求出这个数字。就比如里面有0,1,2,。。。99,100各多少次,但是缺少3这
样的情况。
我只知道brute force,但是不知道如何找出最优化解。 |
k*p 发帖数: 1526 | 2 我觉得brute force挺好,至少scan一遍,不如scan的时候记下个数
【在 l********y 的大作中提到】 : 有一个int array,10000个元素,里面放有数字0到100,但是缺少某一个数字,问怎么 : 样最优求出这个数字。就比如里面有0,1,2,。。。99,100各多少次,但是缺少3这 : 样的情况。 : 我只知道brute force,但是不知道如何找出最优化解。
|
l********y 发帖数: 1327 | |
s*****n 发帖数: 5488 | 4 你的brute force是啥。用个bitmap.如果有就bit[1] = 1,otherwise, bit[i] = 0
这个几乎最快了吧。
【在 l********y 的大作中提到】 : 有一个int array,10000个元素,里面放有数字0到100,但是缺少某一个数字,问怎么 : 样最优求出这个数字。就比如里面有0,1,2,。。。99,100各多少次,但是缺少3这 : 样的情况。 : 我只知道brute force,但是不知道如何找出最优化解。
|
k*p 发帖数: 1526 | 5 bit是个boolean数组么?
最后要再遍历一边check 0值么?
【在 s*****n 的大作中提到】 : 你的brute force是啥。用个bitmap.如果有就bit[1] = 1,otherwise, bit[i] = 0 : 这个几乎最快了吧。
|
L*******e 发帖数: 114 | 6 Either use vector or bitset(need define a const variable though).
just 100 entries, do not think it is a big overhead comparing to scan the
original array.
【在 k*p 的大作中提到】 : bit是个boolean数组么? : 最后要再遍历一边check 0值么?
|
s*****n 发帖数: 5488 | 7 bool也算大。scan一遍也就是100个数。当然,可以提高为
bitmap can be two long.
long[2] bitmap = {OL,OL | binary set bit 100-64 all 1};
....
for(int i = 0; i < 2; i++)
if (~bitmap[i] > 0)
find which big is 1;
【在 k*p 的大作中提到】 : bit是个boolean数组么? : 最后要再遍历一边check 0值么?
|
l********y 发帖数: 1327 | 8 brute force 解法:
int a[10000]已知
int i;
int j;
for(i = 0;i < 100;i++){
for(j = 0;j < 10000;j++){
if(a[j] == i)break;
}
if(j == 10000){
cout << "i is the missing number " << i << endl;
break;
}
}
O(n^2)复杂度,被提示还有更优化解,大概是sort以后binary之类,但是不明白具体,郁闷啊 |
k*p 发帖数: 1526 | 9 想到一个heuristic的算法
设数组为a,定义一个vector b,一个计数器n记录当前找到的出现了的数字的个数
while(n<100) {
if(!b[a[i]]) {
b[a[i]]==true;
n++;
}
i++;
}
当n==100,说明除了那个没有的,其余都出现了,scan可以提前结束
10000个数只有101个可能,如果平均分布,很快就能找到
【在 s*****n 的大作中提到】 : bool也算大。scan一遍也就是100个数。当然,可以提高为 : bitmap can be two long. : long[2] bitmap = {OL,OL | binary set bit 100-64 all 1}; : .... : for(int i = 0; i < 2; i++) : if (~bitmap[i] > 0) : find which big is 1;
|
j*****u 发帖数: 1133 | 10 你这个bruceforce不对啊
开个bool[100]或者bit[100]的数组b,scan一遍b[a[i]] = 1;
然后scan b, when b[j] == 0 return j
【在 l********y 的大作中提到】 : brute force 解法: : int a[10000]已知 : int i; : int j; : for(i = 0;i < 100;i++){ : for(j = 0;j < 10000;j++){ : if(a[j] == i)break; : } : if(j == 10000){ : cout << "i is the missing number " << i << endl;
|
|
|
k*p 发帖数: 1526 | 11 你这个弯绕太大了,每个数字scan一遍
【在 l********y 的大作中提到】 : brute force 解法: : int a[10000]已知 : int i; : int j; : for(i = 0;i < 100;i++){ : for(j = 0;j < 10000;j++){ : if(a[j] == i)break; : } : if(j == 10000){ : cout << "i is the missing number " << i << endl;
|
j*********0 发帖数: 5 | 12 use a hash table to store the 101 numbers?
right?
int FindMiss(int array[],int num=10000)
{
int table[101];
int i;
for (i=0;i<=100;i++)
{
table[i]=0;
}
int j;
for (j=0;j
{
table[array[j]]++;
}
for (i=0;i<=100;i++)
{
if(table[i]==0)
{
return i;
}
}
return i;
} |
L*******e 发帖数: 114 | 13 this is nice!
个数
【在 k*p 的大作中提到】 : 想到一个heuristic的算法 : 设数组为a,定义一个vector b,一个计数器n记录当前找到的出现了的数字的个数 : while(n<100) { : if(!b[a[i]]) { : b[a[i]]==true; : n++; : } : i++; : } : 当n==100,说明除了那个没有的,其余都出现了,scan可以提前结束
|
x*****p 发帖数: 1707 | 14 Complexity is O(n).
You have to scan all 10000 numbers once and then you can get the result. |
l********y 发帖数: 1327 | 15 好方法!
个数
【在 k*p 的大作中提到】 : 想到一个heuristic的算法 : 设数组为a,定义一个vector b,一个计数器n记录当前找到的出现了的数字的个数 : while(n<100) { : if(!b[a[i]]) { : b[a[i]]==true; : n++; : } : i++; : } : 当n==100,说明除了那个没有的,其余都出现了,scan可以提前结束
|