原帖由 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)
原帖由 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)
歡迎光臨 Chinaunix (http://www.72891.cn/) | Powered by Discuz! X3.2 |