LeetCode除自身以外数组的乘积

心已赠人 2023-12-06 07:13 258阅读 0赞

一、题目

给定长度为 n 的整数数组 nums，其中 n > 1，返回输出数组 output ，其中 output[i] 等于 nums 中除 nums[i] 之外其余各元素的乘积。

二、思路

思路：利用2个辅助数组去做。一个保存顺序遍历的乘积，一个保存逆序的乘积（可以一次遍历完成）。

ins[0,0,0,0]

ret[4,4,4,4]

计算后：

ins[1,2,6,24]

ret[24,24,12,4]

三、实现

class Solution {
public:
    vector<int> productExceptSelf(vector<int>& nums) {
        int len=nums.size();
        if(len<=0)return nums;
        vector<int>ins(len,nums[0]);
        vector<int>ret(len,nums[len-1]);
        int mult1=nums[0];
        int mult2=nums[len-1];
        for(int i=1;i<len;i++)
        {
            mult1*=nums[i];
            mult2*=nums[len-i-1];
            ins[i]=mult1;
            ret[len-i-1]=mult2;
        }
        ret[0]=ret[1];
        for(int i=1;i<len-1;i++)
        {
            ret[i]=ins[i-1]*ret[i+1];
        }
        ret[len-1]=ins[len-2];
        return ret;
    }
};