亚洲av成人无遮挡网站在线观看,少妇性bbb搡bbb爽爽爽,亚洲av日韩精品久久久久久,兔费看少妇性l交大片免费,无码少妇一区二区三区

Chinaunix

標題: 遇一算法難題,求救(已解決)哈 [打印本頁]

作者: 1980116    時間: 2007-09-18 09:41
標題: 遇一算法難題,求救(已解決)哈
數(shù)組a[N],存放了1到N-1,其中某個數(shù)重復一次。寫一個函數(shù),找出被重復的數(shù)字.
時間復雜度必須為o(N)函數(shù)原型:
int do_dup(int a[],int N)

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

[ 本帖最后由 1980116 于 2007-9-18 19:27 編輯 ]
作者: dzbjet    時間: 2007-09-18 09:45
樓主說錯了吧,o(N) 復雜度,只需要遍歷數(shù)組,比較就可以了。
作者: cugb_cat    時間: 2007-09-18 09:50
O(N)的復雜度,用另外一個數(shù)組就行了,可能也用不著遍歷,只要碰到有重的就可以停止了
作者: jaffaz    時間: 2007-09-18 09:54
原帖由 1980116 于 2007-9-18 09:41 發(fā)表
數(shù)組a[N],存放了1至N-1個數(shù),其中某個數(shù)重復一次。寫一個函數(shù),找出被重復的數(shù)字.
時間復雜度必須為o(N)函數(shù)原型:
int do_dup(int a[],int N)

已知數(shù)組大小為N,可以得到常數(shù) M=1+2+3+...+(N-2)+(N-1)
把數(shù)組a中的N個元素值相加再減去M即可得到重復的數(shù)字。
算法復雜度為o(N)
作者: 1980116    時間: 2007-09-18 09:59
原帖由 jaffaz 于 2007-9-18 09:54 發(fā)表

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

高明啊,想了好長時間沒有答出來,太厲害了,謝謝你
作者: 柳五隨風    時間: 2007-09-18 10:13
x = N - Sum(1~N) + Sum of the array[N];
作者: ypxing    時間: 2007-09-18 10:26
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
作者: 柳五隨風    時間: 2007-09-18 11:02
標題: 回復 #7 ypxing 的帖子
數(shù)組a[N],存放了1至N-1個數(shù)
所以3不可能出現(xiàn)在array里面。ARRAY里面最大允許的數(shù)字是2。
作者: Sorehead    時間: 2007-09-18 13:20
樓主的描述實在是有問題,大多數(shù)人都會理解錯的。
作者: zhangzhangg    時間: 2007-09-18 13:45
提示: 作者被禁止或刪除 內(nèi)容自動屏蔽




歡迎光臨 Chinaunix (http://www.72891.cn/) Powered by Discuz! X3.2