【LeetCode】算法详解#6 ---除自身以外数组的乘积

1.题目介绍

        给定一个整数数组 nums，返回 数组 answer ，其中 answer[i] 等于 nums 中除 nums[i] 之外其余各元素的乘积 。

题目数据 保证 数组 nums之中任意元素的全部前缀元素和后缀的乘积都在  32 位 整数范围内。

请 不要使用除法，且在 O(n) 时间复杂度内完成此题。

• 2 <= nums.length <= 105
• -30 <= nums[i] <= 30
• 输入 保证 数组 answer[i] 在  32 位 整数范围内

2.解决思路

        既然给定一个数组，让求得每个位置的前缀元素和后缀元素的乘积，实际上就是分别求前缀积和后缀积。我一开始的思路是：如果每次计算前缀积和后缀积的时候都遍历一遍就太浪费时间了，所以就想着如何减少遍历次数，也就是利用前面遍历过的结果，我就想到了“后一个元素的前缀积=前一个元素的前缀积*前一个元素”，这样就可以做到前缀积无需遍历，只需要每次相乘即可。但是这样的问题是由于是从前向后计算，那么后缀积其实是没办法通过这种方式得到的，只能遍历计算，最终时间复杂度还是O(n²)。

        所以换一种思路 ，能不能在计算的时候直接取到前缀积和后缀积，所以可以直接提前进行两次计算，分别计算每个位置的前缀积和后缀积，结合上面的思路，计算前缀积和后缀积的过程都只需要一次遍历即可。最终拿着这两个数组按位置相乘就是最终的答案

3.步骤讲解

        1.先对一些特殊情况进行提前处理

        2.创建前缀积数组和后缀积数组，分别用来存储每个位置的前缀积或者后缀积

        3.初始化结果数组

        4.计算前缀乘积，第一个位置的前缀积为1，后面每个位置的前缀积都是上一个前缀积*上一               个元素值

        5.计算后缀乘积，从后向前计算。最后一个位置的后缀积为1，后面每个位置的前缀积都是后              一个后缀积*后一个元素值。

        6.计算每个位置的前缀积*后缀积，也就是通过索引取得前缀积数组和后缀积数组相乘

4.代码展示

public static int[] test2(int[] nums) {int n = nums.length;if (n == 0) return new int[0];if (n == 1) return new int[]{0};// 创建前缀乘积和后缀乘积数组int[] prefix = new int[n];int[] suffix = new int[n];//结果数组int[] results = new int[n];// 计算前缀乘积prefix[0] = 1;for (int i = 1; i < n; i++) {prefix[i] = prefix[i - 1] * nums[i - 1];}// 计算后缀乘积suffix[n - 1] = 1;for (int i = n - 2; i >= 0; i--) {suffix[i] = suffix[i + 1] * nums[i + 1];}// 计算结果for (int i = 0; i < n; i++) {results[i] = prefix[i] * suffix[i];}return results;}

5.执行结果

在leetcode中测试用例平均耗时2ms

内存分布55.04MB 

 

超时代码示例（O(n²)）：

 public static int[] test(int[] nums) {if (nums.length == 0){return new int[0];}if (nums.length == 1){return new int[]{0};}//先计算所有元素的前缀乘和后缀乘int tempPreMulti = 1;int tempSufMulti = 1;int[] results = new int[nums.length];HashMap<Integer, Integer[]> multi = new HashMap<>();for (int i = 0; i < nums.length; i++) {//计算前缀乘if (i != 0) {tempPreMulti = multi.get(i - 1)[0] * nums[i - 1];}//计算后缀乘for (int j = i+1; j < nums.length; j++) {tempSufMulti  *= nums[j];}multi.put(i, new Integer[]{tempPreMulti, tempSufMulti});//存入数组results[i] = tempPreMulti*tempSufMulti;//重置tempSufMulti = 1;tempPreMulti = 1;}return results;}