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可以提前结束
|
