给定一个数字数组，返回所有其他数字的乘积的数组(不除法)

下面是我尝试用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[i-1]和pj = nums[N-1] * nums[N-2] *.. nums[j+1]。左边的i部分是“前缀”逻辑，右边的j部分是“后缀”逻辑。

递归一行程序

小朋友!给出了一个(漂亮的!)递归解;我把它变成了这样(可怕!)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]"

for(j=0;j<n;j++)
{
prod[j]=1;


for (i=0;i<n;i++)
{
if(i==j)
continue;
else
prod[j]=prod[j]*a[i];
}

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

polygenelubricants方法的解释如下:

诀窍是构造数组(在4个元素的情况下):

{              1,         a[0],    a[0]*a[1],    a[0]*a[1]*a[2],  }
{ a[1]*a[2]*a[3],    a[2]*a[3],         a[3],                 1,  }

这两种方法都可以在O(n)中分别从左右边开始。

然后，将两个数组逐个元素相乘，得到所需的结果。

我的代码看起来是这样的:

int a[N] // This is the input
int products_below[N];
int p = 1;
for (int i = 0; i < N; ++i) {
products_below[i] = p;
p *= a[i];
}


int products_above[N];
p = 1;
for (int i = N - 1; i >= 0; --i) {
products_above[i] = p;
p *= a[i];
}


int products[N]; // This is the result
for (int i = 0; i < N; ++i) {
products[i] = products_below[i] * products_above[i];
}

如果你也需要空间中的解是O(1)，你可以这样做(在我看来不太清楚):

int a[N] // This is the input
int products[N];


// Get the products below the current index
int p = 1;
for (int i = 0; i < N; ++i) {
products[i] = p;
p *= a[i];
}


// Get the products above the current index
p = 1;
for (int i = N - 1; i >= 0; --i) {
products[i] *= p;
p *= a[i];
}

技巧:

使用以下方法:

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

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²)但f#太漂亮了

List.fold (fun seed i -> List.mapi (fun j x -> if i=j+1 then x else x*i) seed)
[1;1;1;1;1]
[1..5]

otherProducts xs = zipWith (*) below above


where below = scanl (*) 1 $ init xs


above = tail $ scanr (*) 1 xs

这里有一个小的递归函数(在c++中)来进行修改。它需要O(n)额外的空间(在堆栈上)。假设数组在a中，并且N保存数组长度，我们有:

int multiply(int *a, int fwdProduct, int indx) {
int revProduct = 1;
if (indx < N) {
revProduct = multiply(a, fwdProduct*a[indx], indx+1);
int cur = a[indx];
a[indx] = fwdProduct * revProduct;
revProduct *= cur;
}
return revProduct;
}

鬼鬼祟祟地绕过“不划分”规则:

sum = 0.0
for i in range(a):
sum += log(a[i])


for i in range(a):
output[i] = exp(sum - log(a[i]))

还有一个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

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

{-
Recursive solution using sqrt(n) subsets. Runs in O(n).


Recursively computes the solution on sqrt(n) subsets of size sqrt(n).
Then recurses on the product sum of each subset.
Then for each element in each subset, it computes the product with
the product sum of all other products.
Then flattens all subsets.


Recurrence on the run time is T(n) = sqrt(n)*T(sqrt(n)) + T(sqrt(n)) + n


Suppose that T(n) ≤ cn in O(n).


T(n) = sqrt(n)*T(sqrt(n)) + T(sqrt(n)) + n
≤ sqrt(n)*c*sqrt(n) + c*sqrt(n) + n
≤ c*n + c*sqrt(n) + n
≤ (2c+1)*n
∈ O(n)


Note that ceiling(sqrt(n)) can be computed using a binary search
and O(logn) iterations, if the sqrt instruction is not permitted.
-}


otherProducts [] = []
otherProducts [x] = [1]
otherProducts [x,y] = [y,x]
otherProducts a = foldl' (++) [] $ zipWith (\s p -> map (*p) s) solvedSubsets subsetOtherProducts
where
n = length a


-- Subset size. Require that 1 < s < n.
s = ceiling $ sqrt $ fromIntegral n


solvedSubsets = map otherProducts subsets
subsetOtherProducts = otherProducts $ map product subsets


subsets = reverse $ loop a []
where loop [] acc = acc
loop a acc = loop (drop s a) ((take s a):acc)

这是我的代码:

int multiply(int a[],int n,int nextproduct,int i)
{
int prevproduct=1;
if(i>=n)
return prevproduct;
prevproduct=multiply(a,n,nextproduct*a[i],i+1);
printf(" i=%d > %d\n",i,prevproduct*nextproduct);
return prevproduct*a[i];
}


int main()
{
int a[]={2,4,1,3,5};
multiply(a,5,1,0);
return 0;
}

下面是一个使用c#的函数式示例:

            Func<long>[] backwards = new Func<long>[input.Length];
Func<long>[] forwards = new Func<long>[input.Length];


for (int i = 0; i < input.Length; ++i)
{
var localIndex = i;
backwards[i] = () => (localIndex > 0 ? backwards[localIndex - 1]() : 1) * input[localIndex];
forwards[i] = () => (localIndex < input.Length - 1 ? forwards[localIndex + 1]() : 1) * input[localIndex];
}


var output = new long[input.Length];
for (int i = 0; i < input.Length; ++i)
{
if (0 == i)
{
output[i] = forwards[i + 1]();
}
else if (input.Length - 1 == i)
{
output[i] = backwards[i - 1]();
}
else
{
output[i] = forwards[i + 1]() * backwards[i - 1]();
}
}

我不是完全确定这是O(n)，由于创建的Funcs的半递归，但我的测试似乎表明，它是O(n)在时间上。

public static void main(String[] args) {
int[] arr = { 1, 2, 3, 4, 5 };
int[] result = { 1, 1, 1, 1, 1 };
for (int i = 0; i < arr.length; i++) {
for (int j = 0; j < i; j++) {
result[i] *= arr[j];


}
for (int k = arr.length - 1; k > i; k--) {
result[i] *= arr[k];
}
}
for (int i : result) {
System.out.println(i);
}
}

我想出了这个解决方案，我发现它很清楚，你觉得呢!?

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

#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和上面的聚基因润滑剂相同的方法)

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)

给你，简单干净的解决方案，复杂度为O(N):

int[] a = {1,2,3,4,5};
int[] r = new int[a.length];
int x = 1;
r[0] = 1;
for (int i=1;i<a.length;i++){
r[i]=r[i-1]*a[i-1];
}
for (int i=a.length-1;i>0;i--){
x=x*a[i];
r[i-1]=x*r[i-1];
}
for (int i=0;i<r.length;i++){
System.out.println(r[i]);
}

这里是Scala中的完整代码:

val list1 = List(1, 2, 3, 4, 5)
for (elem <- list1) println(list1.filter(_ != elem) reduceLeft(_*_))

这将打印出以下内容:

120
60
40
30
24

程序将过滤掉当前的elem (_ != elem);并使用reducleft方法将新列表相乘。我认为这将是O(n)如果你使用scala视图或迭代器进行惰性计算。

//这是Java中的递归解 //从main product(a,1,0)调用

public static double product(double[] a, double fwdprod, int index){
double revprod = 1;
if (index < a.length){
revprod = product2(a, fwdprod*a[index], index+1);
double cur = a[index];
a[index] = fwdprod * revprod;
revprod *= cur;
}
return revprod;
}

O(n)时间的简洁解:

1. 对于每个元素，计算在它之前出现的所有元素的乘积，并将其存储在数组“pre”中。
2. 对于每个元素，计算该元素之后所有元素的乘积，并将其存储在数组“post”中
3. 为元素i创建一个最终数组result，

   result[i] = pre[i-1]*post[i+1];
   

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

O (n)

试试这个!

import java.util.*;
class arrProduct
{
public static void main(String args[])
{
//getting the size of the array
Scanner s = new Scanner(System.in);
int noe = s.nextInt();


int out[]=new int[noe];
int arr[] = new int[noe];


// getting the input array
for(int k=0;k<noe;k++)
{
arr[k]=s.nextInt();
}


int val1 = 1,val2=1;
for(int i=0;i<noe;i++)
{
int res=1;


for(int j=1;j<noe;j++)
{
if((i+j)>(noe-1))
{


int diff = (i+j)-(noe);


if(arr[diff]!=0)
{
res = res * arr[diff];
}
}


else
{
if(arr[i+j]!=0)
{
res= res*arr[i+j];
}
}




out[i]=res;


}
}


//printing result
System.out.print("Array of Product: [");
for(int l=0;l<out.length;l++)
{
if(l!=out.length-1)
{
System.out.print(out[l]+",");
}
else
{
System.out.print(out[l]);
}
}
System.out.print("]");
}


}

下面是我用现代c++编写的解决方案。它使用std::transform，很容易记住。

在线代码(wandbox). .

#include<algorithm>
#include<iostream>
#include<vector>


using namespace std;


vector<int>& multiply_up(vector<int>& v){
v.insert(v.begin(),1);
transform(v.begin()+1, v.end()
,v.begin()
,v.begin()+1
,[](auto const& a, auto const& b) { return b*a; }
);
v.pop_back();
return v;
}


int main() {
vector<int> v = {1,2,3,4,5};
auto vr = v;


reverse(vr.begin(),vr.end());
multiply_up(v);
multiply_up(vr);
reverse(vr.begin(),vr.end());


transform(v.begin(),v.end()
,vr.begin()
,v.begin()
,[](auto const& a, auto const& b) { return b*a; }
);


for(auto& i: v) cout << 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 ]

下面是另一个简单的概念，它解决了O(N)中的问题。

        int[] arr = new int[] {1, 2, 3, 4, 5};
int[] outArray = new int[arr.length];
for(int i=0;i<arr.length;i++){
int res=Arrays.stream(arr).reduce(1, (a, b) -> a * b);
outArray[i] = res/arr[i];
}
System.out.println(Arrays.toString(outArray));

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

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]

根据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)

我有一个解决方案与O(n)空间和O(n^2)时间复杂度如下所示，

public static int[] findEachElementAsProduct1(final int[] arr) {


int len = arr.length;


//        int[] product = new int[len];
//        Arrays.fill(product, 1);


int[] product = IntStream.generate(() -> 1).limit(len).toArray();




for (int i = 0; i < len; i++) {


for (int j = 0; j < len; j++) {


if (i == j) {
continue;
}


product[i] *= arr[j];
}
}


return product;
}

这是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²))，但我想无论如何都要分享。

先转换为List<Integer>。

遍历原始数组array.length()次。

使用while循环来乘下一组所需的数字:

while (temp < list.size() - 1) {
res *= list.get(temp);
temp++;
}

然后将res添加到一个新数组中(当然你在前面已经声明过了)，然后将array[i]的值添加到List中，依此类推。

我知道这不会有太大的用处，但这是我在面试的压力下想到的:)

    int[] array = new int[]{1, 2, 3, 4, 5};
List<Integer> list = Arrays.stream(array).boxed().collect(Collectors.toList());
int[] newarray = new int[array.length];
int res = 1;
for (int i = 0; i < array.length; i++) {
int temp = i;
while (temp < list.size() - 1) {
res *= list.get(temp);
temp++;
}
newarray[i] = res;
list.add(array[i]);
res = 1;
}

输出:[24,120,60,40,30]

添加我的javascript解决方案在这里，因为我没有发现任何人建议这一点。 除法是什么，除了数从另一个数中得到一个数的次数吗?我计算了整个数组的乘积，然后遍历每个元素，并减去当前元素直到0:

//No division operation allowed
// keep substracting divisor from dividend, until dividend is zero or less than divisor
function calculateProducsExceptCurrent_NoDivision(input){
var res = [];
var totalProduct = 1;
//calculate the total product
for(var i = 0; i < input.length; i++){
totalProduct = totalProduct * input[i];
}
//populate the result array by "dividing" each value
for(var i = 0; i < input.length; i++){
var timesSubstracted = 0;
var divisor = input[i];
var dividend = totalProduct;
while(divisor <= dividend){
dividend = dividend - divisor;
timesSubstracted++;
}
res.push(timesSubstracted);
}
return res;
}

我习惯使用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;
}

以下是线性O(n)时间内的简单Scala版本:

def getProductEff(in:Seq[Int]):Seq[Int] = {


//create a list which has product of every element to the left of this element
val fromLeft = in.foldLeft((1, Seq.empty[Int]))((ac, i) => (i * ac._1, ac._2 :+ ac._1))._2


//create a list which has product of every element to the right of this element, which is the same as the previous step but in reverse
val fromRight = in.reverse.foldLeft((1,Seq.empty[Int]))((ac,i) => (i * ac._1,ac._2 :+ ac._1))._2.reverse


//merge the two list by product at index
in.indices.map(i => fromLeft(i) * fromRight(i))


}

这是可行的，因为本质上答案是一个数组，它是左右所有元素的乘积。

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

nums.map { |n| (num - [n]).inject(:*) }

import java.util.Arrays;


public class Pratik
{
public static void main(String[] args)
{
int[] array = {2, 3, 4, 5, 6};      //  OUTPUT: 360  240  180  144  120
int[] products = new int[array.length];
arrayProduct(array, products);
System.out.println(Arrays.toString(products));
}


public static void arrayProduct(int array[], int products[])
{
double sum = 0, EPSILON = 1e-9;


for(int i = 0; i < array.length; i++)
sum += Math.log(array[i]);


for(int i = 0; i < array.length; i++)
products[i] = (int) (EPSILON + Math.exp(sum - Math.log(array[i])));
}
}

输出:

[360, 240, 180, 144, 120]

时间复杂度:O(n)

空间复杂度:O(1)

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

下面是我使用python的简洁解决方案。

from functools import reduce


def excludeProductList(nums_):
after = [reduce(lambda x, y: x*y, nums_[i:]) for i in range(1, len(nums_))] + [1]
before = [1] + [reduce(lambda x, y: x*y, nums_[:i]) for i in range(1, len(nums_))]
zippedList =  list(zip(before, after))
finalList = list(map(lambda x: x[0]*x[1], zippedList))
return finalList

#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.

ruby的解决方案

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

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

JavaScript的一个变体，使用reduce

const getProduct = arr => arr.reduce((acc, value) => acc * value);


const arrayWithExclusion = (arr, node) =>
arr.reduce((acc, val, j) => (node !== j ? [...acc, val] : acc), []);


const getProductWithExclusion = arr => {
let result = [];


for (let i = 0; i < arr.length; i += 1) {
result.push(getProduct(arrayWithExclusion(arr, i)));
}


return result;
};

上下两次。在O(N)完成的工作

private static int[] multiply(int[] numbers) {
int[] multiplied = new int[numbers.length];
int total = 1;


multiplied[0] = 1;
for (int i = 1; i < numbers.length; i++) {
multiplied[i] = numbers[i - 1] * multiplied[i - 1];
}


for (int j = numbers.length - 2; j >= 0; j--) {
total *= numbers[j + 1];
multiplied[j] = total * multiplied[j];
}


return multiplied;
}

我用Javascript想出了两个解决方案，一个有除法，一个没有

// without division
function methodOne(arr) {
return arr.map(item => {
return arr.reduce((result, num) => {
if (num !== item) {
result = result * num;
}
return result;
},1)
});
}


// with division
function methodTwo(arr) {
var mul = arr.reduce((result, num) => {
result = result * num;
return result;
},1)
return arr.map(item => mul/item);
}


console.log(methodOne([1, 2, 3, 4, 5]));
console.log(methodTwo([1, 2, 3, 4, 5]));

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

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

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

抱歉，走路时用手机

<?php
function product($key, $arr)
{
$arr[$key] = 1;
return array_product($arr);
};
$arr = [1, 2, 3, 4, 5];
$newarr = array();




foreach ($arr as $key => $value) {


$newarr[$key] = product($key, $arr);
}
print_r($newarr);