我在一次工作面试中被问到这个问题,我想知道其他人是如何解决这个问题的。我最擅长使用Java,但也欢迎使用其他语言的解决方案。

给定一个数字数组nums,返回一个数字数组products,其中products[i]是所有nums[j]的乘积,j != i。 输入:[1,2,3,4,5] 输出:[(2 * 3 * 4 * 5),(1 * 3 * 4 * 5),(1 * 2 * 4 * 5),(1 * 2 * 3 * 5),(1 * 2 * 3 * 4)] = [120, 60, 40, 30, 24] 你必须在O(N)中不使用除法来做这个。


当前回答

这是ptyhon版本

  # This solution use O(n) time and O(n) space
  def productExceptSelf(self, nums):
    """
    :type nums: List[int]
    :rtype: List[int]
    """
    N = len(nums)
    if N == 0: return

    # Initialzie list of 1, size N
    l_prods, r_prods = [1]*N, [1]*N

    for i in range(1, N):
      l_prods[i] = l_prods[i-1] * nums[i-1]

    for i in reversed(range(N-1)):
      r_prods[i] = r_prods[i+1] * nums[i+1]

    result = [x*y for x,y in zip(l_prods,r_prods)]
    return result

  # This solution use O(n) time and O(1) space
  def productExceptSelfSpaceOptimized(self, nums):
    """
    :type nums: List[int]
    :rtype: List[int]
    """
    N = len(nums)
    if N == 0: return

    # Initialzie list of 1, size N
    result = [1]*N

    for i in range(1, N):
      result[i] = result[i-1] * nums[i-1]

    r_prod = 1
    for i in reversed(range(N)):
      result[i] *= r_prod
      r_prod *= nums[i]

    return result

其他回答

左旅行->右和保持保存产品。称之为过去。- > O (n) 旅行右->左保持产品。称之为未来。- > O (n) 结果[i] =过去[i-1] *将来[i+1] -> O(n) 过去[-1]= 1;和未来(n + 1) = 1;

O(n)

O(n)时间的简洁解:

对于每个元素,计算在它之前出现的所有元素的乘积,并将其存储在数组“pre”中。 对于每个元素,计算该元素之后所有元素的乘积,并将其存储在数组“post”中 为元素i创建一个最终数组result, 结果[i] = pre[i-1]*post[i+1];

def products(nums):
    prefix_products = []
    for num in nums:
        if prefix_products:
            prefix_products.append(prefix_products[-1] * num)
        else:
            prefix_products.append(num)

    suffix_products = []
    for num in reversed(nums):
        if suffix_products:
            suffix_products.append(suffix_products[-1] * num)
        else:
            suffix_products.append(num)
        suffix_products = list(reversed(suffix_products))

    result = []
    for i in range(len(nums)):
        if i == 0:
            result.append(suffix_products[i + 1])
        elif i == len(nums) - 1:
            result.append(prefix_products[i-1])
        else:
            result.append(
                prefix_products[i-1] * suffix_products[i+1]
            )
    return result

JavaScript中使用reduce的变体

const getProduct = arr => arr。Reduce ((acc, value) => acc * value); const arrayWithExclusion = (arr, node) => 加勒比海盗。Reduce ((acc, val, j) => (node !== j ?)[…Acc, val]: Acc), []); const getproductwitheexclusion = arr => { Let result = []; 对于(设I = 0;I < arrr .length;I += 1) { 结果。推动(getProduct (arrayWithExclusion(加勒比海盗,我))); } 返回结果; };

int[] b = new int[] { 1, 2, 3, 4, 5 };            
int j;
for(int i=0;i<b.Length;i++)
{
  int prod = 1;
  int s = b[i];
  for(j=i;j<b.Length-1;j++)
  {
    prod = prod * b[j + 1];
  }
int pos = i;    
while(pos!=-1)
{
  pos--;
  if(pos!=-1)
     prod = prod * b[pos];                    
}
Console.WriteLine("\n Output is {0}",prod);
}