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

Question

我目前正在练习面试问题。附件是我正在处理的问题的屏幕截图我尝试使用嵌套循环的强力方法来重构嵌套循环，但它仍然未能通过强力方法的测试。这是我试过的代码：def get_products_of_all_ints_except_at_index(int_list):# Make a list with the productsproducts = []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 l

print(productexcept([2,3,7,5]))

>> [105, 70, 30, 42]

Answer 2

如果你被允许使用导入和非常丑陋的列表理解，你可以试试这个：

from functools import reduce

l = [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 prod

l = [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 reduce

def 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 products

products = []

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.efgh

a.cd.efgh

ab.d.efgh

ab.c.efgh

abcd.f.gh

abcd.e.gh

abcd.ef.h

abcd.ef.g

从 0 到 N-1 的数字的二进制结构可以得到所需的表达式。

Answer 6

我想出了这个：

def product(larg):

    result = 1

    for n in larg:

        result *= n

    return result

List = [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，您创建了一个列表列表，其中每个列表中都删除了正确的整数。然后你只需用这些子列表的产品构建一个新列表。