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


当前回答

我习惯使用c#:

    public int[] ProductExceptSelf(int[] nums)
    {
        int[] returnArray = new int[nums.Length];
        List<int> auxList = new List<int>();
        int multTotal = 0;

        // If no zeros are contained in the array you only have to calculate it once
        if(!nums.Contains(0))
        {
            multTotal = nums.ToList().Aggregate((a, b) => a * b);

            for (int i = 0; i < nums.Length; i++)
            {
                returnArray[i] = multTotal / nums[i];
            }
        }
        else
        {
            for (int i = 0; i < nums.Length; i++)
            {
                auxList = nums.ToList();
                auxList.RemoveAt(i);
                if (!auxList.Contains(0))
                {
                    returnArray[i] = auxList.Aggregate((a, b) => a * b);
                }
                else
                {
                    returnArray[i] = 0;
                }
            }
        }            

        return returnArray;
    }

其他回答

def productify(arr, prod, i):
    if i < len(arr):
        prod.append(arr[i - 1] * prod[i - 1]) if i > 0 else prod.append(1)
        retval = productify(arr, prod, i + 1)
        prod[i] *= retval
        return retval * arr[i]
    return 1

if __name__ == "__main__":
    arr = [1, 2, 3, 4, 5]
    prod = []
    productify(arr, prod, 0)
    print(prod)

还有一个解决方案,使用除法。有两次遍历。 把所有元素相乘,然后除以每个元素。

ruby的解决方案

a = [1,2,3,4]
result = []
a.each {|x| result.push( (a-[x]).reject(&:zero?).reduce(:*)) }
puts result

我的第一次尝试,用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]

下面是Ruby中的一行程序解决方案。

全国矿工工会。映射{|n| (num - [n]).inject(:*)}