您有一个整数列表，对于每个索引，您想要找到除该索引处的整数之外的每个整数的乘积。（不能使用除法）

Question

我目前正在练习面试问题。附件是我正在处理的问题的屏幕截图

我尝试使用嵌套循环的强力方法来重构嵌套循环，但它仍然未能通过强力方法的测试。

这是我试过的代码：

def get_products_of_all_ints_except_at_index(int_list):

# Make a list with the products

products = []

for i in int_list:

    for j in int_list:

        if(i != j):

            k = int_list[i] * int_list[j]

            products.append(k)

return products

我对蛮力解决方案和不使用嵌套循环的更有效解决方案都很好奇。

Answer 1

使用右侧和左侧累积乘积的线性算法def productexcept(l):    n = len(l)    right = [1]*n    for i in reversed(range(n-1)):        right[i] = right[i + 1] * l[i+1]    #print(right)    prod = 1    for i in range(n):        t = l[i]        l[i] = prod * right[i]        prod *= t    return lprint(productexcept([2,3,7,5]))>> [105, 70, 30, 42]

Answer 2

如果你被允许使用导入和非常丑陋的列表理解，你可以试试这个：from functools import reducel = [1,7,3,4][reduce(lambda x,y: x*y, [l[i] for i in range(len(l)) if i != k],1) for k,el in enumerate(l)]如果不允许使用 functools，则可以编写自己的函数：def prod(x):  prod = 1  for i in x:    prod = prod * i  return prodl = [1,7,3,4][prod([l[i] for i in range(len(l)) if i != k]) for k,el in enumerate(l)]我把这两个解决方案放在一个函数中作为练习留给读者。

Answer 3

这是一个使用递归函数而不是循环的解决方案：from functools import reducedef get_products_of_all_ints_except_at_index(int_list, n=0, results=[]):    new_list = int_list.copy()    if n == len(int_list):        return results    new_list.pop(n)    results.append(reduce((lambda x, y: x * y), new_list))    return get_products_of_all_ints_except_at_index(int_list, n+1, results)int_list = [1, 7, 3, 4]print(get_products_of_all_ints_except_at_index(int_list))# expected results [84, 12, 28, 21]输出：[84, 12, 28, 21]

Answer 4

如果你想获得列表中每个元素的索引，你应该尝试for i in range(len(int_list)). for i in int_list实际上是返回列表中的值而不是索引。所以暴力破解应该是：def get_products_of_all_ints_except_at_index(int_list):# Make a list with the productsproducts = []for i in range(len(int_list)):    k = 1    for j in range(len(int_list)):        if(i != j):            k *= int_list[j]    products.append(k)return products

Answer 5

假设 N 是 2 的幂。蛮力需要 N(N-2) 个产品。您可以通过预先计算元素对的 N/2 乘积，然后是 N/4 对，然后是对，直到剩下一对。这总共需要 N-2 个产品。接下来，您通过以二分法将所需的部分产品相乘来形成所有请求的产品。每个产品需要 Lg(N)-1 次乘法，因此总共有 N(Lg(N)-1) 次乘法。这是一个 O(N Log N) 的解决方案。N=8 的说明：使用 6 次乘法，a  b  c  d  e  f  g  h ab    cd    ef    gh   abcd        efgh然后乘以 16，b.cd.efgha.cd.efghab.d.efghab.c.efghabcd.f.ghabcd.e.ghabcd.ef.habcd.ef.g从 0 到 N-1 的数字的二进制结构可以得到所需的表达式。

Answer 6

我想出了这个：def product(larg):    result = 1    for n in larg:        result *= n    return resultList = [1, 7, 3, 4]N = len(List)BaseList = [List[0:i] + List[i+1:N] for i in range(N)]Products = [product(a) for a in BaseList]print(Products)从输入列表中List，您创建了一个列表列表，其中每个列表中都删除了正确的整数。然后你只需用这些子列表的产品构建一个新列表。