一道面試附加題的另類求解

　　題目：已知一個數組a[N]，構造一個數組b[N]，構造規則：b[i]=a[0]*a[1]*a[2]...a[N]/a[i];

要求：

1、不可以使用除法；

2、時間複雜度為O(n)，空間複雜度為S(0)；

3、除周遊使用的變量外，不可以使用其它變量；

　　看似簡單，想想也廢了一番腦筋。

　　最先想到的是就是原作者想到的方法，代碼如下（用的是VB2008）： 

　 Public Shared Function CacuB1(ByVal A() As Double) As Double()

Dim B(A.Length - 1) As Double

　　　　Dim I As Integer

　　　　B(0) = 1

For I = 0 To A.Length - 1

B(0) *= A(I)

Next

　　　　For I = A.Length - 1 To 0 Step -1

B(I) = B(0) / A(I)

　　　　Return B

End Function

　　這個方法還是比較簡潔的，沒有多餘的代碼。唯一不符合要求的就是用了除法   　　

　　那還是老老實實的用最基本的方法，代碼如下：

　　Public Shared Function CacuB2(ByVal A() As Double) As Double()

　　　　Dim I As Integer, J As Integer

　　　　For I = 0 To A.Length - 1

B(I) = 1

For J = 0 To A.Length - 1

If I <> J Then B(I) *= A(J)

　　　　Next

　　雖然計算量上去了，但沒有用除法。不過算法的時間複雜度為O(N*N)，不符合題目要求。而且這種方法比較死闆，筆者不推薦。

　　想了很久，總是在使用除法和時間複雜度之間沒法平衡。

　　突然，一個念頭一閃而過。除法？轉一個彎如何？轉成減法如何？

　　利用公式S/A=10lgS-lgA

　　于是本題就變成

　　　　S=A(0)*A(1)*A(2)……*A(N)

　　　　B(I)=10lgS-lgA(I)　　

　　代碼如下：

　　Public Shared Function CacuB3(ByVal A() As Double) As Double()

　　　　Dim B(A.Length - 1) As Double

　　　　　　B(0) *= A(I)

　　　　　　B(I) = 10 ^ (Math.Log10(B(0)) - Math.Log10(A(I)))

　　End Function

　　符合題目要求了麼？符合了，沒用除法，時間複雜度也是O(N)。隻是效率稍微低了點。

　　但是效率真的低麼？不見得，VS對Log10函數做了優化，雖然低了點，但是可以忽略不計。

　　利用高中階段的對數公式，另類的解決了該問題。如果誰還有更好的算法，望不吝賜教。大家互相學習，共同提高。

    本文轉自萬倉一黍部落格園部落格，原文連結：http://www.cnblogs.com/grenet/archive/2012/04/07/2436384.html，如需轉載請自行聯系原作者