查找乘法数组的最快方法（按最少操作数计算）

Question

一道面试题：

我有一个数组：例如这个：

a,b,c,d,e,f,g!=0

List_1=[a,b,c,d,e,f,g]

我想找到一个用最少的运算符找到这个结果的最佳方法:

Multiplication=[a+bcdefg,ab+cdefg,abc+defg,abcd+efg,abcde+fg,abcdef+g]

我建议使用这个方法：

mult=a*b*c*d*e*f*g
Multiplication=[]
Temp=List_1[0]
while(i<(len(List_1))-1):
    mult/=List_1[i]
    Multiplication.append(Temp+mult)
    Temp*=List_1[i+1]

这一行mult=a*b*c*d*e*f*g需要$n-1$乘法，while循环需要$(n-1)$乘法，$(n-1)$除法和$(n-1 )$ 添加。所以总时间大约是 $3n-3$ 乘法和 $(n-1)$ 加法。

是这种最简单的方法还是有其他内存和时间最少的方法？

Answer 1

首先创建[a, ab, abc, …]：

l = [a, b, c, d, e, f, g]
result = []
p = 1

for i in range(0, len(l) - 1):
    p *= l[i]
    result.append(p)

然后加上[…, efg, fg, g]:

p = 1

for i in range(len(l) - 1, 0, -1):
    p *= l[i]
    result[i - 1] += p

这需要对列表元素进行 2(n − 1) 次乘法和 n − 1 次加法，优于 2(n − 1) 次乘法、2(n − 1) 次除法和 n − 1 次加法。

这也是Primusa描述的。

Answer 2

建议不除法如下：

myList=[1,2,3,4,5,6,7,8]
arrLen = len(myList)
leftOp = [1] * arrLen
rightOp = [1] * arrLen
result =  [1] * (arrLen - 1)
leftOp[0] = myList[0]
rightOp[arrLen - 1] = myList[arrLen - 1]
for i in range(1, arrLen - 1):
    leftOp[i] = myList[i] * leftOp[i-1]
    rightOp[arrLen - 1 - i] = myList[arrLen - 1 - i] * rightOp[arrLen - i]

for i in range(0, arrLen - 1):
    result[i] = leftOp[i] + rightOp[i + 1]

查找乘法数组的最快方法（按最少操作数计算）

Fastest Method for Find Multiplication Array ( by Minimum Number of Operations)

python

algorithm

time-complexity

multiplication

space-complexity