LeetCode238. Product of Array Except Self

最新推荐文章于 2024-01-03 13:51:22 发布

耀凯考前突击大师

最新推荐文章于 2024-01-03 13:51:22 发布

阅读量359

点赞数

分类专栏： leetcode 文章标签： leetcode

本文链接：https://blog.csdn.net/Yaokai_AssultMaster/article/details/78342402

版权

leetcode 专栏收录该内容

31 篇文章

订阅专栏

本文介绍了一种高效计算数组中除自身以外元素乘积的方法，包括两种两遍扫描算法和一种一遍扫描算法，详细讨论了时间复杂度为O(n)的不同空间复杂度实现方案。

摘要生成于 C知道，由 DeepSeek-R1 满血版支持，前往体验 >

Solution1 Two-pass O(n) time O(n) space

Considering that we are trying to get something like cumulative sum except self, it is possible that we can utilize some method similar to cumulative sum to get this product. So for this product of array except self, we actually want the product of the left side of the array multiplies the product of the right side of the array. Yes! we can use the 2 side cumulative product, i.e. one multiplies from left to right one by one and the other multiplies from right to left one by one. And thus for a specific product except self, we simply get the product of left side and right side.

Time complexity: O(2n) = O(n) because of the 2 passes.
Space complexity: O(2n) = O(n) because of the 2 arrays.

class Solution {
    /**
     * O(n) time, O(n) space 2 pass solution
     * Calculate the left cumulative product and right cumulative product respectively.
     * And then get the product expect self in O(1).
     */
    public int[] productExceptSelf(int[] nums) {
        int product = 1;
        int[] leftProduct = new int[nums.length];
        int[] rightProduct = new int[nums.length];
        // left cumulative product
        for (int i = 1; i <= nums.length - 1; i++) {
            leftProduct[i] = product * nums[i - 1];
            product = leftProduct[i];
        }
        leftProduct[0] = 1;

        product = 1;
        // right cumulative product
        for (int i = nums.length - 2; i >= 0; i--) {
            rightProduct[i] = product * nums[i + 1];
            product = rightProduct[i];
        }
        rightProduct[nums.length - 1] = 1;

        int[] ret = new int[nums.length];
        for (int i = 0; i < nums.length; i++) {
            ret[i] = leftProduct[i] * rightProduct[i];
        }

        return ret;
    }
}

Solution2 Two-pass O(n) time O(1) space without considering the return array

Although we stored the left and right cumulative product in the previous solution, actually since we are only using one right product each time, we can calculate it on the fly, rather than store it. And for the left product, we could override it step by step from right to left to make it stores the return results.

Time complexity: O(2n) = O(n).
Space complexity: O(1) without considering the return array.

class Solution {
    public int[] productExceptSelf(int[] nums) {
        int len = nums.length;
        int[] ret = new int[len];
        ret[0] = 1;
        for (int i = 1; i < len; i++) {
            ret[i] = nums[i - 1] * ret[i - 1];
        }

        int right = 1;
        for (int i = len - 1; i >= 0; i--) {
            ret[i] = ret[i] * right;
            right = right * nums[i];
        }

        return ret;
    }
}

Solution3 One-pass O(n) time O(1) space

Scan the array from left to right in the same for loop.

class Solution {
    public int[] productExceptSelf(int[] nums) {
        int left = 1;
        int right = 1;
        int len = nums.length;
        int[] ret = new int[len];
        Arrays.fill(ret, 1);
        for (int i = 0, j = len - 1; i < len - 1; i++, j--) {
            left *= nums[i];
            right *= nums[j];
            ret[i + 1] *= left;
            ret[j - 1] *= right;
        }

        return ret;
    }
}