遇一算法難題，求救（已解決）哈

1980116

數(shù)組a[N]，存放了1到N-1，其中某個(gè)數(shù)重復(fù)一次。寫(xiě)一個(gè)函數(shù)，找出被重復(fù)的數(shù)字.
時(shí)間復(fù)雜度必須為o（N）函數(shù)原型：
int do_dup(int a[],int N)

例如：n=3,
a[3] ={1,2,2}
找出哪個(gè)數(shù)重復(fù)了

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

dzbjet

樓主說(shuō)錯(cuò)了吧，o(N) 復(fù)雜度，只需要遍歷數(shù)組，比較就可以了。

cugb_cat

O(N)的復(fù)雜度，用另外一個(gè)數(shù)組就行了，可能也用不著遍歷，只要碰到有重的就可以停止了

jaffaz

原帖由 1980116 于 2007-9-18 09:41 發(fā)表
數(shù)組a[N]，存放了1至N-1個(gè)數(shù)，其中某個(gè)數(shù)重復(fù)一次。寫(xiě)一個(gè)函數(shù)，找出被重復(fù)的數(shù)字.
時(shí)間復(fù)雜度必須為o（N）函數(shù)原型：
int do_dup(int a[],int N)

已知數(shù)組大小為N，可以得到常數(shù) M=1+2+3+...+(N-2)+(N-1)
把數(shù)組a中的N個(gè)元素值相加再減去M即可得到重復(fù)的數(shù)字。
算法復(fù)雜度為o(N)

1980116

原帖由 jaffaz 于 2007-9-18 09:54 發(fā)表

已知數(shù)組大小為N，可以得到常數(shù) M=1+2+3+...+(N-2)+(N-1)
把數(shù)組a中的N個(gè)元素值相加再減去M即可得到重復(fù)的數(shù)字。
算法復(fù)雜度為o(N)

高明啊，想了好長(zhǎng)時(shí)間沒(méi)有答出來(lái)，太厲害了，謝謝你

柳五隨風(fēng)

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

柳五隨風(fēng)

數(shù)組a[N]，存放了1至N-1個(gè)數(shù)
所以3不可能出現(xiàn)在array里面。ARRAY里面最大允許的數(shù)字是2。

Sorehead

樓主的描述實(shí)在是有問(wèn)題，大多數(shù)人都會(huì)理解錯(cuò)的。