预先计算每个元素左右两边数字的乘积。 对于每个元素，期望值都是它相邻元素乘积的乘积。

#include <stdio.h>

unsigned array[5] = { 1,2,3,4,5};

int main(void)
{
unsigned idx;

unsigned left[5]
        , right[5];
left[0] = 1;
right[4] = 1;

        /* calculate products of numbers to the left of [idx] */
for (idx=1; idx < 5; idx++) {
        left[idx] = left[idx-1] * array[idx-1];
        }

        /* calculate products of numbers to the right of [idx] */
for (idx=4; idx-- > 0; ) {
        right[idx] = right[idx+1] * array[idx+1];
        }

for (idx=0; idx <5 ; idx++) {
        printf("[%u] Product(%u*%u) = %u\n"
                , idx, left[idx] , right[idx]  , left[idx] * right[idx]  );
        }

return 0;
}

结果:

$ ./a.out
[0] Product(1*120) = 120
[1] Product(1*60) = 60
[2] Product(2*20) = 40
[3] Product(6*5) = 30
[4] Product(24*1) = 24

(更新:现在我仔细看，这使用与Michael Anderson, Daniel Migowski和上面的聚基因润滑剂相同的方法)

我们正在分解数组的元素，首先从下标之前开始，即前缀，然后是下标或后缀之后

class Solution:

   def productExceptSelf(nums):

      length = len(nums)


      result = [1] * length


      prefix_product = 1


      postfix_product = 1

# we initialize the result and products


      for i in range(length)

      result[i] *= prefix_product


       prefix_product *= nums[i]

#we multiply the result by each number before the index

      for i in range(length-1,-1,-1)

      result[i] *= postfix_product


      postfix_product *= nums[i]

#same for after index
   return result

抱歉，走路时用手机

技巧:

使用以下方法:

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，但这是解决它的方法。

使用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 ]

将Michael Anderson的解决方案翻译成Haskell:

otherProducts xs = zipWith (*) below above

     where below = scanl (*) 1 $ init xs

           above = tail $ scanr (*) 1 xs

我们可以先从列表中排除nums[j](其中j != i)，然后得到其余部分的乘积;下面是python解决这个难题的方法:

from functools import reduce
def products(nums):
    return [ reduce(lambda x,y: x * y, nums[:i] + nums[i+1:]) for i in range(len(nums)) ]
print(products([1, 2, 3, 4, 5]))

[out]
[120, 60, 40, 30, 24]