一道面试附加题的另类求解

　有一段时间没有写博客了。今日闲逛的时候，看到一篇博客“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

　　这个方法还是比较简洁的，没有多余的代码。唯一不符合要求的就是用了除法   　　

　　那还是老老实实的用最基本的方法，代码如下：

　　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

　　虽然计算量上去了，但没有用除法。不过算法的时间复杂度为O(N*N)，不符合题目要求。而且这种方法比较死板，笔者不推荐。

　　想了很久，总是在使用除法和时间复杂度之间没法平衡。

　　突然，一个念头一闪而过。除法？转一个弯如何？转成减法如何？

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

　　于是本题就变成

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

　　　　B(I)=10^lgS-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

　　符合题目要求了么？符合了，没用除法，时间复杂度也是O(N)。只是效率稍微低了点。

　　但是效率真的低么？不见得，VS对Log10函数做了优化，虽然低了点，但是可以忽略不计。

　　利用高中阶段的对数公式，另类的解决了该问题。如果谁还有更好的算法，望不吝赐教。大家互相学习，共同提高。

作者：万仓一黍

出处：http://grenet.cnblogs.com/

本文版权归作者和博客园共有，欢迎转载，但未经作者同意必须保留此段声明，且在文章页面明显位置给出原文连接，否则保留追究法律责任的权利。