查找除 Self 之外的数组的乘积

Photo by 克里斯托弗·高尔 on 不飞溅

给定一个 整数 大批 数字 ， 返回 数组 回答 这样 答案[我] 等于所有元素的乘积 数字 除了 数字[i] .

任何前缀或后缀的乘积 数字 是 保证 适应一个 32 位 整数。

您必须编写一个运行在 上） 时间和不使用除法运算。

示例 1：

 输入：nums = [1,2,3,4]  
 输出：[24,12,8,6]

示例 2：

 输入：nums = [-1,1,0,-3,3]  
 输出：[0,0,9,0,0]

跟进： 你能解决这个问题吗 O(1) 额外的空间复杂度？ （输出数组 才不是 算作空间复杂度分析的额外空间。）

解决方案：

这里的主要技巧是 O(n) 时间并且不使用除法运算。

我将尝试画出主要思想。

我将在这个解决方案中使用额外的空间，但我们可以稍后改进算法并移除额外的内存。

我们将从左到右将元素相乘，然后从右到尾 exept self 元素

如果我们准备 leftArr 并从左侧到右侧相乘元素会怎样。

 0. 数字 = [1,2,3,4]  
 1.leftArr = [1,1,1,1]  
 2.leftArr = [1,1,1*2,1*2*3]  
 3.leftArr = [1,1,2,6]

然后我们可以准备 rightArr 并从右边向左边相乘。

 0. 数字 = [1,2,3,4]  
 1.rightArr = [1,1,1,1]  
 2.rightArr = [1,1,1*4,1]  
 3. rightArr = [1,1*3*4,4,1]  
 3.rightArr = [1*2*3*4,1*3*4,4,1]  
 4.rightArr = [24,12,4,1]

然后，我们应该遍历两个数组并将元素相乘

 0.leftArr = [1,1,2,6]  
 1.leftArr = [24,12,4,1]  
 2. rez = [24, 12, 8, 6]

似乎是一个明智的决定，不是吗？

当然，还有它的代码。

 公共 int[] productExceptSelf(int[] nums) {  
 int 长度 = nums.length;  
 int[] toRight = new int[length];  
 int[] toLeft = new int[length];  
 向右[0] = 1;  
 for(int i = 1; i < 长度; i++){  
 toRight[i] = toRight[i-1] * nums[i-1];  
 }  
 toLeft[长度 - 1] = 1;  
 for(int i = 长度 - 2; i >= 0; i--){  
 toLeft[i] = toLeft[i+1] * nums[i+1];  
 }  
      
 for(int i = 0; i < 长度; i++){  
 toRight[i] = toRight[i] * toLeft[i];  
 }  
 回到右边；  
 }

使用这种方法，我们可以在不使用 ‘+’ 或 ‘*’ 的情况下找到数组中的元素的总和或相乘

手术。

但是我们该如何改进呢？

现在，我们使用另外两个数组，这很好。让我们尝试降低内存复杂度。

在不创建两个数组的情况下，我们只能创建一个数组。再次，遍历基本数组并从左到右将元素相乘。

 公共 int[] productExceptSelf(int[] nums) {  
 int[] ans = new int[nums.length];  
 整数左= 1；  
          
 for (int i = 0; i < nums.length; i++) {  
 ans[i] = 左；  
 左 *= 数字 [i];  
 }  
          
 诠释正确 = 1;  
 for (int i = nums.length - 1; i >= 0; i--) {  
 ans[i] *= 对；  
 对 *= 数字 [i];  
 }  
          
 返回答案；  
 }

运行时间：1 毫秒，比 Java 在线提交的 Array 除了 Self 的产品快 100.00%。
内存使用量：50 MB，少于 Java 在线提交的 Product of Array except Self 的 59.22%

这个概念很简单，您想从左侧和右侧（不包括自身）计算产品。 ans[i] 是左 * 右。

我希望你们很清楚。如果您有不清楚的地方，请写评论，我会尽力回答。

版权声明：本文为博主原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明

本文链接：https://www.qanswer.top/32262/18341301