我在一次工作面试中被问到这个问题,我想知道其他人是如何解决这个问题的。我最擅长使用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)中不使用除法来做这个。


当前回答

技巧:

使用以下方法:

public int[] calc(int[] params) {

int[] left = new int[n-1]
in[] right = new int[n-1]

int fac1 = 1;
int fac2 = 1;
for( int i=0; i<n; i++ ) {
    fac1 = fac1 * params[i];
    fac2 = fac2 * params[n-i];
    left[i] = fac1;
    right[i] = fac2; 
}
fac = 1;

int[] results = new int[n];
for( int i=0; i<n; i++ ) {
    results[i] = left[i] * right[i];
}

是的,我确定我错过了一些I -1而不是I,但这是解决它的方法。

其他回答

我的第一次尝试,用Python。O (2 n):

def product(l):
    product = 1
    num_zeroes = 0
    pos_zero = -1

    # Multiply all and set positions
    for i, x in enumerate(l):
        if x != 0:
            product *= x
            l[i] = 1.0/x
        else:
            num_zeroes += 1
            pos_zero = i

    # Warning! Zeroes ahead!
    if num_zeroes > 0:
        l = [0] * len(l)

        if num_zeroes == 1:
            l[pos_zero] = product

    else:
        # Now set the definitive elements
        for i in range(len(l)):
            l[i] = int(l[i] * product)

    return l


if __name__ == "__main__":
    print("[0, 0, 4] = " + str(product([0, 0, 4])))
    print("[3, 0, 4] = " + str(product([3, 0, 4])))
    print("[1, 2, 3] = " + str(product([1, 2, 3])))
    print("[2, 3, 4, 5, 6] = " + str(product([2, 3, 4, 5, 6])))
    print("[2, 1, 2, 2, 3] = " + str(product([2, 1, 2, 2, 3])))

输出:

[0, 0, 4] = [0, 0, 0]
[3, 0, 4] = [0, 12, 0]
[1, 2, 3] = [6, 3, 2]
[2, 3, 4, 5, 6] = [360, 240, 180, 144, 120]
[2, 1, 2, 2, 3] = [12, 24, 12, 12, 8]

这是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

c++, O (n):

long long prod = accumulate(in.begin(), in.end(), 1LL, multiplies<int>());
transform(in.begin(), in.end(), back_inserter(res),
          bind1st(divides<long long>(), prod));

还有一个O(N^(3/2))非最优解。不过,这很有趣。

首先预处理大小为N^0.5的每个部分乘法(这在O(N)时间复杂度中完成)。然后,计算每个数字的其他值的倍数可以在2*O(N^0.5)时间内完成(为什么?因为您只需要将其他((N^0.5) - 1)数字的最后一个元素相乘,并将结果与属于当前数字组的((N^0.5) - 1)数字相乘。对每一个数都这样做,可以得到O(N^(3/2))时间。

例子:

4, 6, 7, 2, 3, 1, 9, 5, 8

部分结果: 4*6*7 = 168 2*3*1 = 6 9*5*8 = 360

要计算3的值,需要将其他组的值乘以168*360,然后乘以2*1。

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);
}