根据Billz的回答——抱歉我不能评论，但这里是一个正确处理列表中重复项的scala版本，可能是O(n):

val list1 = List(1, 7, 3, 3, 4, 4)
val view = list1.view.zipWithIndex map { x => list1.view.patch(x._2, Nil, 1).reduceLeft(_*_)}
view.force

返回:

List(1008, 144, 336, 336, 252, 252)

    int[] arr1 = { 1, 2, 3, 4, 5 };
    int[] product = new int[arr1.Length];              

    for (int i = 0; i < arr1.Length; i++)
    {
        for (int j = 0; j < product.Length; j++)
        {
            if (i != j)
            {
                product[j] = product[j] == 0 ? arr1[i] : product[j] * arr1[i];
            }
        }
    }

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)

使用EcmaScript 2015编码

'use strict'

/*
Write a function that, given an array of n integers, returns an array of all possible products using exactly (n - 1) of those integers.
*/
/*
Correct behavior:
- the output array will have the same length as the input array, ie. one result array for each skipped element
- to compare result arrays properly, the arrays need to be sorted
- if array lemgth is zero, result is empty array
- if array length is 1, result is a single-element array of 1

input array: [1, 2, 3]
1*2 = 2
1*3 = 3
2*3 = 6
result: [2, 3, 6]
*/
class Test {
  setInput(i) {
    this.input = i
    return this
  }
  setExpected(e) {
    this.expected = e.sort()
    return this
  }
}

class FunctionTester {
  constructor() {
    this.tests = [
      new Test().setInput([1, 2, 3]).setExpected([6, 3, 2]),
      new Test().setInput([2, 3, 4, 5, 6]).setExpected([3 * 4 * 5 * 6, 2 * 4 * 5 * 6, 2 * 3 * 5 * 6, 2 * 3 * 4 * 6, 2 * 3 * 4 * 5]),
    ]
  }

  test(f) {
    console.log('function:', f.name)
    this.tests.forEach((test, index) => {
      var heading = 'Test #' + index + ':'
      var actual = f(test.input)
      var failure = this._check(actual, test)

      if (!failure) console.log(heading, 'input:', test.input, 'output:', actual)
      else console.error(heading, failure)

      return !failure
    })
  }

  testChain(f) {
    this.test(f)
    return this
  }

  _check(actual, test) {
      if (!Array.isArray(actual)) return 'BAD: actual not array'
      if (actual.length !== test.expected.length) return 'BAD: actual length is ' + actual.length + ' expected: ' + test.expected.length
      if (!actual.every(this._isNumber)) return 'BAD: some actual values are not of type number'
      if (!actual.sort().every(isSame)) return 'BAD: arrays not the same: [' + actual.join(', ') + '] and [' + test.expected.join(', ') + ']'

      function isSame(value, index) {
        return value === test.expected[index]
      }
  }

  _isNumber(v) {
    return typeof v === 'number'
  }
}

/*
Efficient: use two iterations of an aggregate product
We need two iterations, because one aggregate goes from last-to-first
The first iteration populates the array with products of indices higher than the skipped index
The second iteration calculates products of indices lower than the skipped index and multiplies the two aggregates

input array:
1 2 3
   2*3
1*    3
1*2

input array:
2 3 4 5 6
    (3 * 4 * 5 * 6)
(2) *     4 * 5 * 6
(2 * 3) *     5 * 6
(2 * 3 * 4) *     (6)
(2 * 3 * 4 * 5)

big O: (n - 2) + (n - 2)+ (n - 2) = 3n - 6 => o(3n)
*/
function multiplier2(ns) {
  var result = []

  if (ns.length > 1) {
    var lastIndex = ns.length - 1
    var aggregate

    // for the first iteration, there is nothing to do for the last element
    var index = lastIndex
    for (var i = 0; i < lastIndex; i++) {
      if (!i) aggregate = ns[index]
      else aggregate *= ns[index]
      result[--index] = aggregate
    }

    // for second iteration, there is nothing to do for element 0
    // aggregate does not require multiplication for element 1
    // no multiplication is required for the last element
    for (var i = 1; i <= lastIndex; i++) {
      if (i === 1) aggregate = ns[0]
      else aggregate *= ns[i - 1]
      if (i !== lastIndex) result[i] *= aggregate
      else result[i] = aggregate
    }
  } else if (ns.length === 1) result[0] = 1

  return result
}

/*
Create the list of products by iterating over the input array

the for loop is iterated once for each input element: that is n
for every n, we make (n - 1) multiplications, that becomes n (n-1)
O(n^2)
*/
function multiplier(ns) {
  var result = []

  for (var i = 0; i < ns.length; i++) {
    result.push(ns.reduce((reduce, value, index) =>
      !i && index === 1 ? value // edge case: we should skip element 0 and it's the first invocation: ignore reduce
      : index !== i ? reduce * value // multiply if it is not the element that should be skipped
      : reduce))
  }

  return result
}

/*
Multiply by clone the array and remove one of the integers

O(n^2) and expensive array manipulation
*/
function multiplier0(ns) {
  var result = []

  for (var i = 0; i < ns.length; i++) {
    var ns1 = ns.slice() // clone ns array
    ns1.splice(i, 1) // remove element i
    result.push(ns1.reduce((reduce, value) => reduce * value))
  }

  return result
}

new FunctionTester().testChain(multiplier0).testChain(multiplier).testChain(multiplier2)

使用Node.js v4.4.5运行:

Node—harmony integerarrays.js

function: multiplier0
Test #0: input: [ 1, 2, 3 ] output: [ 2, 3, 6 ]
Test #1: input: [ 2, 3, 4, 5, 6 ] output: [ 120, 144, 180, 240, 360 ]
function: multiplier
Test #0: input: [ 1, 2, 3 ] output: [ 2, 3, 6 ]
Test #1: input: [ 2, 3, 4, 5, 6 ] output: [ 120, 144, 180, 240, 360 ]
function: multiplier2
Test #0: input: [ 1, 2, 3 ] output: [ 2, 3, 6 ]
Test #1: input: [ 2, 3, 4, 5, 6 ] output: [ 120, 144, 180, 240, 360 ]

下面是我尝试用Java来解决这个问题。抱歉格式不规范，但代码有很多重复，这是我能做的最好的，使它可读。

import java.util.Arrays;

public class Products {
    static int[] products(int... nums) {
        final int N = nums.length;
        int[] prods = new int[N];
        Arrays.fill(prods, 1);
        for (int
           i = 0, pi = 1    ,  j = N-1, pj = 1  ;
           (i < N)         && (j >= 0)          ;
           pi *= nums[i++]  ,  pj *= nums[j--]  )
        {
           prods[i] *= pi   ;  prods[j] *= pj   ;
        }
        return prods;
    }
    public static void main(String[] args) {
        System.out.println(
            Arrays.toString(products(1, 2, 3, 4, 5))
        ); // prints "[120, 60, 40, 30, 24]"
    }
}

循环不变量为pi = nums[0] * nums[1] *..* nums[N-2] *..num [j + 1]。左边的i部分是“前缀”逻辑，右边的j部分是“后缀”逻辑。

递归一行程序

Jasmeet给出了一个(漂亮的!)递归解;我把它变成了这样(可怕!)Java一行程序。它进行就地修改，堆栈中有O(N)个临时空间。

static int multiply(int[] nums, int p, int n) {
    return (n == nums.length) ? 1
      : nums[n] * (p = multiply(nums, nums[n] * (nums[n] = p), n + 1))
          + 0*(nums[n] *= p);
}

int[] arr = {1,2,3,4,5};
multiply(arr, 1, 0);
System.out.println(Arrays.toString(arr));
// prints "[120, 60, 40, 30, 24]"

下面是一个C实现 O(n)时间复杂度。 输入

#include<stdio.h>
int main()
{
    int x;
    printf("Enter The Size of Array : ");
    scanf("%d",&x);
    int array[x-1],i ;
    printf("Enter The Value of Array : \n");
      for( i = 0 ; i <= x-1 ; i++)
      {
          printf("Array[%d] = ",i);
          scanf("%d",&array[i]);
      }
    int left[x-1] , right[x-1];
    left[0] = 1 ;
    right[x-1] = 1 ;
      for( i = 1 ; i <= x-1 ; i++)
      {
          left[i] = left[i-1] * array[i-1];
      }
    printf("\nThis is Multiplication of array[i-1] and left[i-1]\n");
      for( i = 0 ; i <= x-1 ; i++)
      {
        printf("Array[%d] = %d , Left[%d] = %d\n",i,array[i],i,left[i]);
      }
      for( i = x-2 ; i >= 0 ; i--)
      {
          right[i] = right[i+1] * array[i+1];
      }
   printf("\nThis is Multiplication of array[i+1] and right[i+1]\n");
      for( i = 0 ; i <= x-1 ; i++)
      {
        printf("Array[%d] = %d , Right[%d] = %d\n",i,array[i],i,right[i]);
      }
    printf("\nThis is Multiplication of Right[i] * Left[i]\n");
      for( i = 0 ; i <= x-1 ; i++)
      {
          printf("Right[%d] * left[%d] = %d * %d = %d\n",i,i,right[i],left[i],right[i]*left[i]);
      }
    return 0 ;
}

输出

    Enter The Size of Array : 5
    Enter The Value of Array :
    Array[0] = 1
    Array[1] = 2
    Array[2] = 3
    Array[3] = 4
    Array[4] = 5

    This is Multiplication of array[i-1] and left[i-1]
    Array[0] = 1 , Left[0] = 1
    Array[1] = 2 , Left[1] = 1
    Array[2] = 3 , Left[2] = 2
    Array[3] = 4 , Left[3] = 6
    Array[4] = 5 , Left[4] = 24

    This is Multiplication of array[i+1] and right[i+1]
    Array[0] = 1 , Right[0] = 120
    Array[1] = 2 , Right[1] = 60
    Array[2] = 3 , Right[2] = 20
    Array[3] = 4 , Right[3] = 5
    Array[4] = 5 , Right[4] = 1

    This is Multiplication of Right[i] * Left[i]
    Right[0] * left[0] = 120 * 1 = 120
    Right[1] * left[1] = 60 * 1 = 60
    Right[2] * left[2] = 20 * 2 = 40
    Right[3] * left[3] = 5 * 6 = 30
    Right[4] * left[4] = 1 * 24 = 24

    Process returned 0 (0x0)   execution time : 6.548 s
    Press any key to continue.