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

Question

我在求职面试中被问到这个问题，我想知道其他人如何解决这个问题。我对Java最熟悉，但欢迎使用其他语言的解决方案。

给定一组数字，nums返回一个数字数组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)不使用除法的情况下这样做。

Answer 1

polygenelubricants方法的解释是：诀窍是构造数组（在4个元素的情况下）{&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; 1,&nbsp; &nbsp; &nbsp; &nbsp; &nbsp;a[0],&nbsp; &nbsp; a[0]*a[1],&nbsp; &nbsp; a[0]*a[1]*a[2],&nbsp; }{ a[1]*a[2]*a[3],&nbsp; &nbsp; a[2]*a[3],&nbsp; &nbsp; &nbsp; &nbsp; &nbsp;a[3],&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;1,&nbsp; }通过分别从左边缘和右边缘开始，可以在O（n）中完成这两个操作。然后将两个数组逐个元素相乘，得到所需的结果我的代码看起来像这样：int a[N] // This is the inputint products_below[N];p=1;for(int i=0;i<N;++i) {&nbsp; products_below[i]=p;&nbsp; p*=a[i];}int products_above[N];p=1;for(int i=N-1;i>=0;--i) {&nbsp; products_above[i]=p;&nbsp; p*=a[i];}int products[N]; // This is the resultfor(int i=0;i<N;++i) {&nbsp; products[i]=products_below[i]*products_above[i];}如果你需要在太空中是O（1）你也可以这样做（这不太清楚恕我直言）int a[N] // This is the inputint products[N];// Get the products below the current indexp=1;for(int i=0;i<N;++i) {&nbsp; products[i]=p;&nbsp; p*=a[i];}// Get the products above the curent indexp=1;for(int i=N-1;i>=0;--i) {&nbsp; products[i]*=p;&nbsp; p*=a[i];}

Answer 2

这是一个小的递归函数（在C ++中）来进行修改。它需要O（n）额外空间（在堆栈上）。假设数组在a中并且N保持数组长度，我们有int multiply(int *a, int fwdProduct, int indx) {&nbsp; &nbsp; int revProduct = 1;&nbsp; &nbsp; if (indx < N) {&nbsp; &nbsp; &nbsp; &nbsp;revProduct = multiply(a, fwdProduct*a[indx], indx+1);&nbsp; &nbsp; &nbsp; &nbsp;int cur = a[indx];&nbsp; &nbsp; &nbsp; &nbsp;a[indx] = fwdProduct * revProduct;&nbsp; &nbsp; &nbsp; &nbsp;revProduct *= cur;&nbsp; &nbsp; }&nbsp; &nbsp; return revProduct;}

Answer 3

这是我尝试用Java解决它。抱歉为非标准格式化，但代码有很多重复，这是我能做的最好的，使它可读。import java.util.Arrays;public class Products {&nbsp; &nbsp; static int[] products(int... nums) {&nbsp; &nbsp; &nbsp; &nbsp; final int N = nums.length;&nbsp; &nbsp; &nbsp; &nbsp; int[] prods = new int[N];&nbsp; &nbsp; &nbsp; &nbsp; Arrays.fill(prods, 1);&nbsp; &nbsp; &nbsp; &nbsp; for (int&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;i = 0, pi = 1&nbsp; &nbsp; ,&nbsp; j = N-1, pj = 1&nbsp; ;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;(i < N)&nbsp; &nbsp; &nbsp; &nbsp; &nbsp;&& (j >= 0)&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; ;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;pi *= nums[i++]&nbsp; ,&nbsp; pj *= nums[j--]&nbsp; )&nbsp; &nbsp; &nbsp; &nbsp; {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;prods[i] *= pi&nbsp; &nbsp;;&nbsp; prods[j] *= pj&nbsp; &nbsp;;&nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; &nbsp; &nbsp; return prods;&nbsp; &nbsp; }&nbsp; &nbsp; public static void main(String[] args) {&nbsp; &nbsp; &nbsp; &nbsp; System.out.println(&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; Arrays.toString(products(1, 2, 3, 4, 5))&nbsp; &nbsp; &nbsp; &nbsp; ); // prints "[120, 60, 40, 30, 24]"&nbsp; &nbsp; }}循环不变量是pi = nums[0] * nums[1] *.. nums[i-1]和pj = nums[N-1] * nums[N-2] *.. nums[j+1]。i左边的部分是“前缀”逻辑，j右边的部分是“后缀”逻辑。递归单行Jasmeet给出了一个（漂亮！）递归解决方案; 我把它变成了这个（丑陋的）Java单线程。它使用堆栈中的临时空间进行就地修改O(N)。static int multiply(int[] nums, int p, int n) {&nbsp; &nbsp; return (n == nums.length) ? 1&nbsp; &nbsp; &nbsp; : nums[n] * (p = multiply(nums, nums[n] * (nums[n] = p), n + 1))&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; + 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]"