leetcode 238. Product of Array Except Self

拼搏现实的明天。 2022-06-13 03:08 141阅读 0赞

# 1.题目 #

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\].  
给一个长度为n的数组nums，求output\[i\]，output\[i\]为出了nums\[i\]以外的所有其他元素的乘积  
Solve it without division and in O(n).  
要求不使用除法，在时间复杂度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.)

# 2.分析 #

没想到好方法，看了solution。  
output\[i-1\], output\[i\]  
output\[i-1\]=nums\[0\]\*nums\[1\]..\*nums\[i-2\]\*nums\[i\]…\*nums\[n-1\]  
output\[i\]=nums\[0\]\*nums\[1\]..\*nums\[i-1\]\*nums\[i+1\]…\*nums\[n-1\]  
把结果的计算拆成小于i 和大于i的两部分  
prefix\[i-1\]=nums\[0\]\*nums\[1\]…\*nums\[i-2\]  
prefix\[i\]=nums\[0\]\*nums\[1\]…\*nums\[i-2\]\*nums\[i-1\]  
所以prefix\[i\]=prefix\[i-1\]\*nums\[i-1\]

suffix\[i-1\]=nums\[i\]\*nums\[i+1\]…\*nums\[n-1\]  
suffix\[i\]=nums\[i+1\]…\*nums\[n-1\]  
所以suffix\[i-1\]=suffix\[i\]\*nums\[i\]

# 3.代码 #

class Solution {
    public:
        vector<int> productExceptSelf(vector<int>& nums) {
            vector<int> ans(nums.size(), 1);
            int prefix = 1;
            for (int i = 0; i < nums.size(); i++) {
                ans[i] = prefix;
                prefix *= nums[i];
            }
            int suffix = 1;
            for (int i = nums.size()-1; i >= 0; i--) {
                ans[i] *= suffix;
                suffix *= nums[i];
            }
            return ans;
        }
    };