Leetcode 238 Product of Array Except Self 时间O(n)和空间O(1)解法

全栈程序员-用户IM • 2022年1月30日下午6:00 • 未分类

大家好，又见面了，我是全栈君。

1. 问题描写叙述

　　给定一个n个整数的数组（

n>1
)nums，返回一个数组output，当中的元素

outputi
的值为原数组nums中除

numsi
之外的全部元素的积。比如：nums数组为[1,2,3,4]。返回的output数组为[24,12,8,6]。

　　要求不用除法和时间复杂度为O(n).
　

2. 方法与思路

　　这道题假设没有除法的限制的话就非常easy了，先求全部数的乘积，然后除以

numsi
。考虑一下除数为零的情况，非常好解决。
　　

class Solution {
public:
    vector<int> productExceptSelf(vector<int>& nums) {
        vector<int> re;
        long mul=1;
        int zeroNum = 0;

        for(int i=0; i < nums.size(); i++)
        {
            if(nums[i] != 0) mul *= nums[i];
            else zeroNum++;
        }

        for(int i = 0; i < nums.size(); i++)
        {
            if(zeroNum > 1) re.push_back(0);
            else if(zeroNum == 1)
            {
                if(nums[i] == 0) re.push_back(mul);
                else re.push_back(0);
            }
            else 
                re.push_back(mul/nums[i]);
        }
        return re;
    }
};

　　可是题目上明白要求不能用除法，那我们得另辟蹊径了。以下以数组[1,2,3,4,5]为例，看完以下表述就明白了：

扫描顺序	1	2	3	4	5
从左至右	1	1×1	1×1×2	1×1×2×3	1×1×2×3×4
从右至左	1×(2×3×4×5)	(1×1）×(3×4×5)	(1×1×2)×(4×5)	(1×1×2×3)×(5)	(1×1×2×3×4)×(1)

　　
　　就是先从左至右扫描，记录前

i−1
个数的乘积，第二遍扫描时，从右至左。将乘积再乘以后

i+1
位的乘积。
　　

class Solution {
public:
    vector<int> productExceptSelf(vector<int>& nums) {
        vector<int> re(nums.size(),1);
        int i,tmp = 1;

        for(i = 1; i < nums.size(); i++)
            re[i] =re[i-1] * nums[i-1];

        for(i = nums.size()-1; i >= 0; i--)
            re[i] *= tmp,tmp *= nums[i];

        return re;
    }
};