简单编程,求解!
数组a[N]，存放了1至N-1个数，其中某个数重复一次。写一个函数，找出被重复的数字.时间复杂度必须为o（N）函数原型：

[解决办法]
const int N = 5;
int a[N]={2,1,3,1,4};
int tmp1 = 0;
int tmp2 = 0;
for (int i=0; i <N; ++i)
{
tmp1+=(i+1);
tmp2+=a[i];
}
printf( "重复的数:%d\n ",N-(tmp1-tmp2));
[解决办法]
先对数组a[N]求和,然后减去sum(1,...,N-1),也就是N(N-1)/2,得到的就是被重复的那个数.

[解决办法]
sum1 = 1+2+..+N-1;
sum2 = a[0]+a[1]+..+a[N];

sum2-sum1 就是结果了
[解决办法]
楼主，你自己好好看看你的题目，数组a[N]，存放了1至N-1个数，其中某个数重复一次，你的这个数组{2,5,5,3}符合你的题目吗？请问？N=4，那应该放的是1--3之间的数才对，怎么会出现5啊？？？晕
按照你题目的意思就应该这样解决：先对数组a[N]求和,然后减去sum(1,...,N-1),也就是N(N-1)/2,得到的就是被重复的那个数.
[解决办法]
liufei1108(无泪) ( ) 信誉：100 2007-09-02 14:19:57 得分: 0


楼主，你自己好好看看你的题目，数组a[N]，存放了1至N-1个数，其中某个数重复一次，你的这个数组{2,5,5,3}符合你的题目吗？请问？N=4，那应该放的是1--3之间的数才对，怎么会出现5啊？？？晕
按照你题目的意思就应该这样解决：先对数组a[N]求和,然后减去sum(1,...,N-1),也就是N(N-1)/2,得到的就是被重复的那个数.

请问数组{2,5,5,3}为什么不符合题目呢
为什么N=4就一定存放1-3的数呢
题说“存放了1至N-1个数”不是存放1至N-1的数自然数..注意是个，是数量单位的“个”



[解决办法]
这个用C++的map就可以了。
假设a[N]是int类型的。代码如下：

#include < map >
#include < iostream >
using namespace std;

int main()
{
const int N = 5;
map < int, int > valueMap;
int a[N] = { 3, 6, 9, 1, 6 };

for( int i = 0; i < N; i ++ )
{
valueMap[a[i]] ++;
}

for( i = 0; i < N; i ++ )
{
if( valueMap[a[i]] > 1 )
{
cout < < a[i] < < endl;
break;
}
}

return 0;
}
[解决办法]
有种笨办法

int temp[M]:1; //M足够大，或者对允许输入a[N]的最大值作限定max[a[n]] <M

int i;
for(i=0;i <N;i++)
{
if(temp[a[i]] == 1)
{
printf( "重复数字是：%d\n ",a[i]);
break;
}
temp[a[i]] == 1;
}