leet code 238. 除自身以外数组的乘积

238.除自身以外数组的乘积

题目解析

• 题目要求 O(n) 的时间复杂度完成
• 进阶：O(1) 空间复杂度 完成

先不想那么多，先按照暴力思路来一遍

• 对于每一个元素，要求得除自身以外数组的乘积，那么可以遍历所有剩下的元素进行相乘，然后得出结果

• 这样的话 时间复杂度 来到了：
• 显然不行

• 直接算出所有元素的乘积，再除以 当前元素是可以的，但是又不允许用除法
• 看了下 题目标签：前缀和

• 但是如何运用前缀和呢？
• 想不出来啊

• 倒着想，首先的话，肯定是需要进行计算的。遍历一遍数组元素。
• 对于任意一个元素的话

• 要想求：除自身以外数组的乘积
• 那么可以进行换算：其左边所有元素的乘积 * 其右边所有元素的乘积 = 除自身以外数组的乘积
• 那么的话可以创建两个数组分别代表

• 左前缀积和
• 右前缀积和

• 如下图

show code

class Solution {
    public int[] productExceptSelf(int[] nums) {
        int n = nums.length;
        int[] left = new int[n];
        int[] right = new int[n];

        // 首先求左前缀积
        int ans = 1;
        for(int i = 0;i < n;i++) {
            left[i] = ans * nums[i];
            ans = left[i];
        }

        ans = 1;
        // 求右前缀积
        for(int i = n - 1;i >= 0;i--) {
            right[i] = ans * nums[i];
            ans = right[i];
        }

        int[] ret = new int[n];
        for (int i = 0; i < n; i++) {
            int leftIdx = i - 1;
            int rightIdx = i + 1;
            ret[i] = (leftIdx < 0 ? 1 : left[leftIdx]) * (rightIdx == n ? 1 : right[rightIdx]);
        }

        return ret;
    }
}

进阶实现

• 通过 O(n) 的空间复杂度解决了问题。
• 如果通过 O(1) 的空间复杂度解决呢？
• 直观地，通过O(1) 的空间复杂度解决的话，需要两个变量 来分别代替 左前缀积和右前缀积 数组
• 那么如何实现这一操作呢？好像不是那么简单

学习官解

• 有一个重要信息
• 输出的数组将不被视为额外空间

• 那么的话，可以用输出数组作为辅助来计算.

public int[] best(int[] nums) {
        int n = nums.length;
        int[] ans = new int[n];

        // ans[i] 表示索引 i 左侧所有元素的乘积
        // 索引 0 左边没有元素，所以初始化为  1
        ans[0] = 1;

        for (int i = 1; i < n; i++) {
            ans[i] = ans[i - 1] * nums[i - 1];
        }

        // right 为右侧所有元素的乘积
        // 初始化 右侧没有元素，right = 1
        int right = 1;
        for(int i = n - 1;i >= 0;i--) {
            // 对于索引 i , 左边的乘积为 ans[i] , 右边的乘积为 right
            ans[i] = ans[i] * right;

            // 计算右边的乘积
            right *= nums[i];
        }

        return ans;
    }