遇一算法难题，求救（已解决）哈

1980116

数组a[N]，存放了1到N-1，其中某个数重复一次。写一个函数，找出被重复的数字.
时间复杂度必须为o（N）函数原型：
int do_dup(int a[],int N)

例如：n=3,
a[3] ={1,2,2}
找出哪个数重复了

[ 本帖最后由 1980116 于 2007-9-18 19:27 编辑 ]

dzbjet

楼主说错了吧，o(N) 复杂度，只需要遍历数组，比较就可以了。

cugb_cat

O(N)的复杂度，用另外一个数组就行了，可能也用不着遍历，只要碰到有重的就可以停止了

jaffaz

原帖由 1980116 于 2007-9-18 09:41 发表
数组a[N]，存放了1至N-1个数，其中某个数重复一次。写一个函数，找出被重复的数字.
时间复杂度必须为o（N）函数原型：
int do_dup(int a[],int N)

已知数组大小为N，可以得到常数 M=1+2+3+...+(N-2)+(N-1)
把数组a中的N个元素值相加再减去M即可得到重复的数字。
算法复杂度为o(N)

1980116

原帖由 jaffaz 于 2007-9-18 09:54 发表

已知数组大小为N，可以得到常数 M=1+2+3+...+(N-2)+(N-1)
把数组a中的N个元素值相加再减去M即可得到重复的数字。
算法复杂度为o(N)

高明啊，想了好长时间没有答出来，太厉害了，谢谢你

柳五随风

x = N - Sum(1~N） + Sum of the array[N];

ypxing

4楼和6楼的方法正确吗???
1,2,3

a[N]=2, 3, 3

4楼:
M=1+2=3
a[N]: 2+3+3=8



6楼:
N:3
Sum(1~N）:1+2+3=6
Sum of the array[N]:2+3+3=8
3-6+8=5

柳五随风

数组a[N]，存放了1至N-1个数
所以3不可能出现在array里面。ARRAY里面最大允许的数字是2。

Sorehead

楼主的描述实在是有问题，大多数人都会理解错的。