在一組連續的數字中(如從1到10000)去掉某一個值,將去掉的值放到一個數組中,求出去掉的那個值。
這是一道很經典的題,相信大家都知道怎麼做。目前我看的最好的做法有兩種:
一、求和相減法:將1到10000這10000個數相加得到數a;然後將數組中的數相加得到數b;最後a-b就是我們要求的值。但是,這種最後存在一個問題,就是可能存在越界的問題,當上界很大的時候很肯尼個造成相加操作越界。所以有了第二種解法。
二、輔助數組法:將從1到10000這1萬個數放入到一個數組中,然後將新數組和原數組位位相減,最後得出了值就是我們要求的值。但是,這種解法的空間復雜度是O(n)。
那麼有沒有一種解法可以是時間復雜度O(n),空間復雜度是O(1),且不越界的算法呢?答案是肯定的。因為,我們可以利用原數組的下標。
分析:
設數組元素從大到小以此為{x1,x2,....,xk-1,xk+1,...,xn},xk即為所缺少的值
y1=x1+x2+...+xk-1+xk+1,...+xn
y2=x1+x2+...+xk-1+xk+xk+1,...+xn
y3=x1+x2+...+xk-1+xk+xk+1,...+xn-1
則xk=y2-y1=y3-y1+xn
其中,y3就是原數組的下標之和,我們可以很容易在不分別計算出y3和y1值的情況下,計算出y3-y1。
而xn其實就是數組的長度。
至此,可得出所求的值xk
算法如下:(這裡我們假設更一般的情況,這些連續的數字不是從1開始,而是可以從任意數字開始)
#include <cstdlib><iostream> FindLose( *a, len, main( argc, * a[] ={,,,,,,, l = FindLose(a,,<< FindLose( a[], len, sum=( i=;i<len;i+++=((i+start)- sum+(start+