有一段时间没有写博客了。今日闲逛的时候，看到一篇博客“4月7日某公司在华南地区举办了一年一度的"开发者"聚会——记某公司笔试”。里面有作者回忆的面试题。其中一题引起了笔者的注意，题目如下：
题目：已知一个数组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)
Next
Return B
End Function
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)
Next
Return B
End Function
这个方法还是比较简洁的，没有多余的代码。唯一不符合要求的就是用了除法
那还是老老实实的用最基本的方法，代码如下：
Public
Shared
Function CacuB2(
ByVal A()
As
Double)
As
Double()
Dim B(A.Length - 1) 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
Next
Return B
End Function
Dim B(A.Length - 1) 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
Next
Return B
End Function
虽然计算量上去了，但没有用除法。不过算法的时间复杂度为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
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) = 10 ^ (Math.Log10(B(0)) - Math.Log10(A(I)))
Next
Return B
End Function
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) = 10 ^ (Math.Log10(B(0)) - Math.Log10(A(I)))
Next
Return B
End Function
符合题目要求了么？符合了，没用除法，时间复杂度也是O(N)。只是效率稍微低了点。
但是效率真的低么？不见得，VS对Log10函数做了优化，虽然低了点，但是可以忽略不计。
利用高中阶段的对数公式，另类的解决了该问题。如果谁还有更好的算法，望不吝赐教。大家互相学习，共同提高。
