LeetCode-238 Product of Array Except Self

题目描述

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

题目大意

根据所给的数组，计算出一个新的数组output[n]，其中output[i] = nums[0] * nums[1] * ... * nums[i - 1] * nums[i + 1] * ... nums[n - 1]，即除了位置i的数字，其余所有位置的数字相乘的结果。

（要求不能用除法，并在O（N）的时间复杂度完成算法）

（最好空间复杂度也是O（1））

示例

E1

解题思路

需要遍历两边原始数组，第一次将当前位置之前所有位置的数字之积保存在结果数组output中，第二遍需要逆序遍历，只需要一个变量保存该位置之后所有数字之积，并将该变量乘output当前位置的结果，即可得到最终结果。具体看代码。

复杂度分析

时间复杂度：O(N)

空间复杂度：O(1)

代码

class Solution {
public:
    vector<int> productExceptSelf(vector<int>& nums) {
        int n = nums.size();
        // res就是结果数组，也就是题目中的output数组
        vector<int> res(n, 1);
        // 第一次顺序遍历，将当前访问位置之前的数字之积保存在res数组中
        for(int i = 1; i < n; ++i) {
            res[i] = res[i - 1] * nums[i - 1];
        }
        // 用变量after保存当前位置之后数字之积
        int after = 1;
        // 逆序遍历，将当前位置的数字乘上after可得到除去当前位置数字其余数字之积
        for(int i = n - 1; i >= 0; --i) {
            res[i] *= after;
            after *= nums[i];
        }
        
        return res;
    }
};