238 Product of Array Except Self 除自身以外数组的乘积

一个长度为 n 的整形数组nums，其中 n > 1，返回一个数组 output ，其中 output[i] 等于nums中除nums[i]以外所有元素的乘积。
不用除法且在O(n)内解决这个问题。
例如，输入 [1,2,3,4]，返回 [24,12,8,6]。
进阶：
你可以在常数空间复杂度内解决这个问题吗？（注意：出于空间复杂度分析的目的，输出数组不被视为额外空间。）
详见：https://leetcode.com/problems/product-of-array-except-self/description/

Java实现：

class Solution {

    public int[] productExceptSelf(int[] nums) {

        int n=nums.length;

        int[] f=new int[n];

        int[] b=new int[n];

        int[] r=new int[n];

        Arrays.fill(f,1);

        Arrays.fill(b,1);

        for(int i=0;i<n-1;++i){

            f[i+1]=f[i]*nums[i];

        }

        for(int i=n-1;i>0;--i){

            b[i-1]=b[i]*nums[i];

        }

        for(int i=0;i<n;++i){

            r[i]=f[i]*b[i];

        }

        return r;

    }

}

C++实现：

class Solution {

public:

    vector<int> productExceptSelf(vector<int>& nums) {

        int n=nums.size();

        vector<int> f(n,1),b(n,1),res(n);

        for(int i=0;i<n-1;++i)

        {

            f[i+1]=f[i]*nums[i];

        }

        for(int i=n-1;i>0;--i)

        {

            b[i-1]=b[i]*nums[i];

        }

        for(int i=0;i<n;++i)

        {

            res[i]=f[i]*b[i];

        }

        return res;

    }

};

参考：https://www.cnblogs.com/grandyang/p/4650187.html

巴特西

238 Product of Array Except Self 除自身以外数组的乘积

最新文章

热门文章