取出a[0],一个一个的和后面的比较，如果没有相等的就再取出a[1],重复上面的比较。
如果a[i]==a[i+n];return a[i];

大家看看上面的算法行么？在网吧上网的。只能写个思路大家讨论。

我也是在网吧，而且好多功能被锁了

LS的看下算法有问题吗？打算回去写下试试

全是弱智算法！


数组a[N]，存放了1至N-1个数

剩下一个数是重复的

那么直接把 1至N-1个数 加起来（等差数列求和），得到 a1

最后把数组 a[N] 的 总和 求出来，得到 a2

重复的数 ＝ a2 － a1

能解释下这个算法吗？

回楼上，4楼的代码是利用a[n]必定<n的特点来做标记
把搜索过的a[i]保存在a[a[i]]上，使用原数据加上n来标记
所以有flag=a[i]%N，以去掉标记得到原数
所以这个算法实质是直接统计，所用的空间是n，只不过直接借用了传递过来的数组。

不过还有一种只要O(1)空间的办法，时间复杂度同样O(n)的

[此贴子已经被作者于2007-8-23 10:34:04编辑过]

数组a[N]，存放了1至N-1个数，其中某个数重复一次。写一个函数，找出被重复的数字

等差数列求和不好

[此贴子已经被作者于2007-8-23 10:49:07编辑过]

恩，可以

[此贴子已经被作者于2007-8-23 10:43:16编辑过]

yes. Editted and tested in VS 2005 and then copy and paste.

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];
}
a[0]为监视哨

[此贴子已经被作者于2007-8-23 10:54:48编辑过]