给定一组数字，返回所有其他数字的产品数组（无分区）
在面试中我被问到了这个问题，我想知道别人怎么解决这个问题。 我对Java非常满意，但是欢迎使用其他语言的解决scheme。
给定一组数字num，返回数组
products，其中products[i]是所有nums[j], j != i的乘积。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]你必须在
O(N)做这个，而不使用划分。
对polygenelubricants方法的解释是：诀窍是构造arrays（在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]; 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 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]; }
这里是一个小的recursion函数（用C ++）来进行修改。 尽pipe它需要O（n）额外的空间（在堆栈上）。 假设数组是在一个和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; }
这是我尝试在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部分是“后缀”逻辑。
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]"
将Michael Anderson的解决scheme翻译成Haskell：
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]))
在这里，你去，简单和干净的解决scheme与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]); }
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 ^ 2），但f＃太漂亮了：
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]
这是我在现代C ++中的解决scheme。 它使用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 << " "; }
- 旅行左 – >右，并继续保存产品。 称它为过去。 – > O（n）
- 旅行权 – >保留产品。 称它为未来。 – > O（n）
- 结果[i] =过去[i-1] *未来[i + 1] – > O（n）
- 过去[-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]; }
是的，我确定我错过了一些I-1，而不是我，但那是解决它的方法。
还有一个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
部分结果：4 * 6 * 7 = 168 2 * 3 * 1 = 6 9 * 5 * 8 = 360
要计算3的值，需要将其他组的值168 * 360乘以2 * 1。
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); } }
这个解决scheme我想出来，我发现它很清楚你怎么看？！
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
那么这个解决scheme可以被认为是C / C ++的。 假设我们有一个包含n个元素（如[n]）的数组“a”，那么伪代码将如下所示。
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]; }
多一个解决scheme，使用部门。 两次遍历。 乘以所有的元素，然后开始分割每个元素。
{ -
使用sqrt（n）子集的recursion解决scheme。 运行在O（n）。
recursion地计算sqrt（n）大小为sqrt（n）的子集上的解决scheme。
然后recursion每个子集的乘积和。
然后为每个子集中的每个元素计算产品
所有其他产品的产品总和。
然后弄平所有子集。
在运行时间上的重复是T（n）= sqrt（n）* T（sqrt（n））+ T（sqrt（n））+ n
假设O（n）中的T（n）≤cn。
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
＆在; 上）
请注意，ceiling（sqrt（n））可以使用二进制search来计算
和O（logn）迭代，如果sqrt指令不被允许的话。
- }
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; }
这是一个稍微有用的例子，使用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](); } }
由于创build的Funcs的半recursion，我不完全确定这是O（n），但是我的testing似乎表明它是O（n）。
预先计算每个元素左侧和右侧的数字的乘积。 对于每个元素来说，所需的价值都是它的产品。
#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一样）
这里要完成的是Scala中的代码：
val list1 = List(1, 2, 3, 4, 5) for (elem <- list1) println(list1.filter(_ != elem) reduceLeft(_*_))
这将打印出以下内容：
120 60 40 30 24
程序会过滤掉当前的elem（_！= elem）; 并用reduceLeft方法乘以新的列表。 我认为这将是O（n）如果你使用scala视图或迭代器来进行惰性评估。
//这是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：
- 对于每个元素计算之前发生的所有元素的乘积，并将其存储在数组“pre”中。
- 对于每个元素，计算在该元素之后发生的所有元素的乘积并将其存储在数组“post”
-
创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("]"); } }
这是另一个简单的概念，它解决了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 ：
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]
基于比尔兹的回答 – 对不起，我不能评论，但这是一个正确处理列表中重复项目的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)时间复杂度下面提供的解决scheme，
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]; } } }
