一次遍历查找不同的数问题
admin 发表于 2010-04-21 | 来源：互联网 | 阅读：
输入一组偶数个的数，其中只有一对数是不同的，其他的都是成对出现。
数字的范围：0~INT_MAX
数字的个数：2~2000000个
如输入1 2 3 2 2 3
输出1 2
如果是用数组存数，数组最大只能开1000000这么大的。如何一遍扫描就能找出不同的两个数？
公告牌:
输入一组偶数个的数，其中只有一对数是不同的，其他的都是成对出现。
数字的范围：0~INT_MAX
数字的个数：2~2000000个
如输入1 2 3 2 2 3
输出1 2
如果是用数组存数，数组最大只能开1000000这么大的。如何一遍扫描就能找出不同的两个数？
评论功能因故关闭！
请加入我们的QQ群一起参与讨论：群号59400482（500人超级群）
假设目标数组为dec[1000000]新建一个数组key，大小为INT_MAX扫描一次数组while(i<1000000)key[dec[i]]++;再扫描key，输出key[i] 不为2的数只想到这个
可以用map
可是这样就要开两个数组（一个1000000,一个INT_MAX），而系统的要求是最大就能开1000000，超过这么大就会判断出错的
关于数的个数，定长数组是在堆栈中分配的，大小有限制，动态分配一个数组就是了，
用map比较好，第一次出现的数直接当作key；循环一次，直接用key匹配，匹配到的直接将其从map中删掉最后map中剩下的2个，就是那不成对的一对了
数组多大没有关系， 一个malloc 搞掂。这一题用map 性能应该差不多，或者更低吧
C/C++ code
int size=6;
int *arr=new int[size];
arr[0]=2;
arr[1]=2;
arr[2]=3;
arr[3]=2;
arr[4]=2;
arr[5]=3;
int cur=-1,next=0;
while(next<size)
{
if (cur==-1) arr[++cur]=arr[next++];
else if (arr[cur]==arr[next]) cur–,next++;
else
{
if (cur+1==next) cur++,next++;
else arr[++cur]=arr[next++];
}
}
for (int i=0;i<=cur;i++)
cout<<arr[i]<<endl;
C/C++ code
delete arr;
能不能用位运算呢？
就是总数除以2的数组，再加一个标志位，表示不同的个数。以为最多不同的是总数除以2那么多。就是说的以空间来代替时间的浪费。
C/C++ code
#include <stdio.h>
#include <stdlib.h>
int main()
{
int n;
while(scanf("%d", &n) != -1 && n)
{
int diffx[32] = {0}, diffy[32] = {0};
int select = 0;
for(int i = 0; i < 2 * n; ++i)
{
int x;
scanf("%d", &x);
select ^= x;
for(int j = 0; j < 32; ++j)
{
if(x & (1 << j))
{
diffx[j] ^= x;
}
else
{
diffy[j] ^= x;
}
}
}
int a = 0, b = 0;
for(int j = 0; j < 32; ++j)
{
if(select & (1 << j))
{
a = diffx[j];
b = diffy[j];
break;
}
}
if(b < a) { int t = a; a = b; b = t; }
printf("%d %d\n", a, b);
}
return 0;
}
终于找到了我想要的了呵呵
帮顶。