【leetcode81】Product of Array Except Self

谁借莪１个温暖的怀抱￠ 2022-04-11 06:41 174阅读 0赞

# 题目描述： #

## 给定一个长度为n的整数数组Array【】，输出一个等长的数组result【】，这个输出数组，对应位置i是除了Array【i】之外，其他的所有元素的乘积 ##

## 例如： ##

given \[1,2,3,4\], return \[24,12,8,6\].

## 要求： ##

时间复杂度是o（n）

# 原文描述： #

Given an array of n integers where n > 1, nums, return an array output such that output\[i\] is equal to the product of all the elements of nums except nums\[i\].

## Solve it without division and in O(n). ##

For example, given \[1,2,3,4\], return \[24,12,8,6\].

## Follow up: ##

Could you solve it with constant space complexity? (Note: The output array does not count as extra space for the purpose of space complexity analysis.)

# 思路1： #

*  考虑构造两个数组相乘来解决
 *  例如nums=\[a1,a2,a3,a4\]，构造的数组是：  
    \[1, a1, a1\*a2, a1\*a2\*a3\]  
    \[a2\*a3\*a4, a3\*a4, a4, 1\]
 *  上面的数组相乘，得到\[a2\*a3\*a4, a1\*a3\*a4, a1\*a2\*a4, a1\*a2\*a3\]

public class Solution {
        public int[] productExceptSelf(int[] nums) {
            final int[] result = new int[nums.length];
            final int[] left = new int[nums.length];
            final int[] right = new int[nums.length];
    
            left[0] = 1;
            right[nums.length - 1] = 1;
    
            for (int i = 1; i < nums.length; ++i) {
                left[i] = nums[i - 1] * left[i - 1];
            }
    
            for (int i = nums.length - 2; i >= 0; --i) {
                right[i] = nums[i + 1] * right[i + 1];
            }
    
            for (int i = 0; i < nums.length; ++i) {
                result[i] = left[i] * right[i];
            }
    
            return result;
        }
    }

# 思路2：（空间复杂度o（1）） #

*  考虑上面的第二个数组的数据用一个常数代替，然后输出的数组，是不算空间的

# 代码： #

public class Solution {
        public int[] productExceptSelf(int[] nums) {
             final int[] left = new int[nums.length];
            left[0] = 1;
    
            for (int i = 1; i < nums.length; ++i) {
                left[i] = nums[i - 1] * left[i - 1];
            }
    
            int right = 1;
            for (int i = nums.length - 1; i >= 0; --i) {
                left[i] *= right;
                right *= nums[i];
            }
            return left;
        }
    }

参考：  
[https://soulmachine.gitbooks.io/algorithm-essentials/content/java/linear-list/array/product-of-array-except-self.html][https_soulmachine.gitbooks.io_algorithm-essentials_content_java_linear-list_array_product-of-array-except-self.html]

# 更多leetcode题目，请看我的leetcode专栏。链接如下： #

[https_soulmachine.gitbooks.io_algorithm-essentials_content_java_linear-list_array_product-of-array-except-self.html]: https://soulmachine.gitbooks.io/algorithm-essentials/content/java/linear-list/array/product-of-array-except-self.html