#include<stdio.h>
#define N 10
void main()
{
int a[N]={1,2,3,4,5,6,7,7,8,9};
int pi[N]={0};
int key=0;
for(int i=0;i<N;i++)
{
if(pi[a[i]]==0)
pi[a[i]]=a[i];
else
{
key=a[i];
break;
}
}

printf("多余的数字是%d\n",key);
}
[我不喜欢…………]

[此贴子已经被作者于2007-8-23 12:01:00编辑过]

存放了1至N-1个数

题目容易有歧义，不知道楼主是什么意思？

HJin在8楼的回复是对的，用的是比较容易的做标记法，空间复杂度是O(n)

学技术的在11楼的方法是最笨的，不符合要求，因为时间复杂度是O(n^2)

福尔摩斯在14楼的理解和大家不一样，我们理解的是放1～N中的N-1个数，哪一个数缺失哪一个数重复不确定，他直接理解为放1～N-1这几个数，没有最后一个数N。楼主说“存放了1至N-1个数”本来也没说清楚。还是理解为第一种比较有意思，像福尔摩斯那样理解这个问题太简单没意义，思科不会出这么简单的题吧。

雨中飞燕在16楼的解释是对的，我和lzyssy在一个实验室，我们讨论的是空间复杂度要低于O(n),所以就出来这么个算法。

我推荐！

晕死。。。。为什么还用void main??

/** Assume we are using the first understanding of the problem:

"我们理解的是放1～N中的N-1个数，哪一个数缺失哪一个数重复不确定."

Then see bugs for different algorithms below.

All algorithms using sums of numbers are subject to overflow problem: assuming
N = 1e9.
*/

#include <iostream>
#include "hjns.h"
using namespace std;

/** bug for lzyssy's algo:

20 9 11 10 16 12 6 2 1 14 5 17 19 8 18 4 3 15 13 7
20 9 11 10 16 12 6 2 1 14 5 17 19 8 18 4 3 15 7 7
重复的数字为 0
重复的数字为 7
Press any key to continue . . .

16 12 8 14 4 7 11 20 1 3 5 18 15 6 19 2 17 10 13 9
16 12 8 14 4 7 11 20 1 3 5 18 15 6 19 9 17 10 13 9
重复的数字为 7
重复的数字为 9
Press any key to continue . . .
*/
void search(int N, int a[])
{
int i,flag;
for(i=0;i<N;i++)
{
flag=a[i]%N;
if(a[flag]<N)
a[flag]+=N;
else
printf("重复的数字为%3d\n",flag);
}
}

/** bug for lishizelibin's algo:

crashed for input:

4 7 12 8 14 3 6 5 19 17 2 1 15 16 20 10 11 18 9 13
4 7 12 13 14 3 6 5 19 17 2 1 15 16 20 10 11 18 9 13

20 6 9 15 7 5 11 16 19 2 10 17 4 8 12 18 14 13 3 1
20 6 9 15 7 5 11 16 19 2 10 17 4 8 12 18 14 13 1 1

*/
int do_dup(int a[],int N)
{
int temp;
while (a[0]!=a[a[0]])
{
temp = a[0];
a[0] = a[temp];
a[temp] = temp;
}
return a[0];
}

int main()
{
const int kSize = 20;
int a[kSize];
int rndIdx;

hj::number::randPerm(a, kSize);
hj::number::random rd;
hj::print(a, kSize);

rndIdx = rd(0, kSize-2);
a[rndIdx] = a[kSize-1];
hj::print(a, kSize);

search(kSize, a);

//printf("%d\n", do_dup(a, kSize));

return 0;
}

我认为福尔摩斯的理解是有道理的，题目中既然说“存放了1至N-1个数”而不是“存放了N-1个数”，就是一个限定，不然应该说是数组a[N]里存放了N个数，其中有两个相同就可以了，而题目没有这么说反而用一个更繁琐的说法，说明命题是有意这样描述的，招聘时会有这种陷阱题甚至是无解题。

lishizelibin 24楼的那个方法有问题，比如N=10,因为没有说数组中的数是递增有序，当a[0]=10就一下越界完蛋了。

因为lishizelibin把老谭的c看了5遍，所以死性不改，至今坚持用void main，呵呵。

assuming
N = 1e9.


HJin佩服你！

[此贴子已经被作者于2007-8-23 11:35:41编辑过]

修改了那错，越界的问题不会那样绝吧，呵呵
int do_dup(int a[],int N)
{
int temp=0,i;
for(i=0;i<N;i++)
{ if(a[i]>=N)
temp=a[i]-N;
else
temp=a[i];
if(a[temp]<N)
{
a[temp]+=N;
}
else
{
printf("do-up!\n");
return temp;
}
}
printf("no do-up!\n");
return -1;
}
这会有什么问题呢？谢谢
以上我贴的是我在学数据结构时积累的算法修改，分析交流！
关于那void，我已经改了
那时以前的程序

[此贴子已经被作者于2007-8-23 12:17:01编辑过]