# 给定一组数字，返回所有其他数字的产品数组（无分区）

` `Input : [1, 2, 3, 4, 5] Output: [(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]` `

` `{ 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, }` `

` `int a[N] // This is the input int products_below[N]; 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]; }` `

` `int a[N] // This is the input int products[N]; // Get the products below the current index p=1; for(int i=0;i<N;++i) { products[i]=p; p*=a[i]; } // Get the products above the curent index p=1; for(int i=N-1;i>=0;--i) { products[i]*=p; p*=a[i]; }` `

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

` `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]" } }` `

### recursion一行

Jasmeet给了一个（漂亮！）recursion解决scheme; 我把它变成了这个（丑陋的！）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]"` `

` `otherProducts xs = zipWith (*) below above where below = scanl (*) 1 \$ init xs above = tail \$ scanr (*) 1 xs` `

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

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

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

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

` `#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 << " "; }` `
1. 旅行左 – >右，并继续保存产品。 称它为过去。 – > O（n）
2. 旅行权 – >保留产品。 称它为未来。 – > O（n）
3. 结果[i] =过去[i-1] *未来[i + 1] – > O（n）
4. 过去[-1] = 1; 和Future [n + 1] = 1;

` `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[ni]; 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]; }` `

4 6 7 2 3 1 9 5 8

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

` `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` `

arr = [1，2，3，4，5] prod = [] productify（arr，prod，0）print prod

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

``` { -

recursion地计算sqrt（n）大小为sqrt（n）的子集上的解决scheme。

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
＆在; 上）

- }

otherProducts [] = []
otherProducts [x] = [1]
otherProducts [x，y] = [y，x]
otherProducts a = foldl'（++）[] \$ zipWith（\ sp  - > map（* p）s）resolvedSubsets subsetOtherProducts
哪里
n =长度a

- 子集大小。 要求1 <s <n。
s =天花板\$ sqrt \$ fromInteral n

solveSubsets = map otherProducts子集
subsetOtherProducts = otherProducts \$ map产品子集

子集= reverse \$ loop a []
其中loop [] acc = acc
循环一个acc =循环（drop sa）（（take sa）：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; }` `

` ` 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](); } }` `

` `#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和polygenelubricants一样）

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

` `120 60 40 30 24` `

//这是Java中的recursion解决scheme//从主产品（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）运行时的整洁解决scheme：

1. 对于每个元素计算之前发生的所有元素的乘积，并将其存储在数组“pre”中。
2. 对于每个元素，计算在该元素之后发生的所有元素的乘积并将其存储在数组“post”
3. 创build一个最终数组“结果”，对于一个元素我，

` `result[i] = pre[i-1]*post[i+1];` `
` `function solution(\$array) { \$result = []; foreach(\$array as \$key => \$value){ \$copyOfOriginalArray = \$array; unset(\$copyOfOriginalArray[\$key]); \$result[\$key] = multiplyAllElemets(\$copyOfOriginalArray); } return \$result; } /** * multiplies all elements of array * @param \$array * @return int */ function multiplyAllElemets(\$array){ \$result = 1; foreach(\$array as \$element){ \$result *= \$element; } return \$result; } \$array = [1, 9, 2, 7]; print_r(solution(\$array));` `

` `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("]"); } }` `

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

` `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]` `

` `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)` `

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