c**********e
发帖数: 2007 | 1 How to find the missing two efficiently? |
L**********u
发帖数: 194 | |
x*****i
发帖数: 287 | 3 //b[1000] is the one we want to check
//
int a[1000] = {0};
for (int i = 0； i < 1000; i++ )
{
a[b[i]] = 1;
}
for (int i = 0; i < 1000; i++ )
{
if(a[i] == 0)
cout << "missing number : " << i << endl;
}
// don't know whether it is a sufficient algorithm or not. It is O(n) |
c**********e
发帖数: 2007 | 4 Could you please post the answer on the green book? Thanks a lot!!!!!
Urgent help needed.
【在 L**********u 的大作中提到】
: 这不是绿皮书上的原题吗？
|
d*j
发帖数: 13780 | 5 要是没有重复的 就列个方程组
sum(x_i) = 一个常数
sum(x_i^2) = 另外一个常数
【在 c**********e 的大作中提到】
: Could you please post the answer on the green book? Thanks a lot!!!!!
: Urgent help needed.
|
L**********u
发帖数: 194 | |
l*****a
发帖数: 14598 | 7 First ,i think the issue is that we have int a[998]
a[0]..a[997] store the number from 1..1000,missed 2 and no duplication
The best way from Computer science is below:
###pay attention that a^a=0
int result=0;
for(int i=0;i<997;i++)
{
result = result ^ a[i];
}
for(int i=1;i<1001;i++)
{
result = result ^ i;
}
###then result is just missing number1 ^ missing number2.
since they are different,there must be one digit is not the same of the two
number.
int index=1;
if!(result & 1<
### now index is the first different digit of number1/number2
###I will divide all the number into two group bu this digit,
then number1/number2 are the only missing number in their group
int result1=0;
int result2=0;
for(int i=0;i<997;i++)
{
if(a[i] & 1<
else result2 = result2 ^ a[i];
}
for(int i=1;i<1001;i++)
{
if(i & 1<
else result2 = result2 ^ i;
}
result1,result2 are just the two missing number
time complexity O(n)
space complexity O(1)
【在 c**********e 的大作中提到】
: How to find the missing two efficiently?
|
l*****a
发帖数: 14598 | 8 u need extra space
【在 x*****i 的大作中提到】
: //b[1000] is the one we want to check
: //
: int a[1000] = {0};
: for (int i = 0； i < 1000; i++ )
: {
: a[b[i]] = 1;
: }
: for (int i = 0; i < 1000; i++ )
: {
: if(a[i] == 0)
|
