剑指66：构建乘积数组

传送门

nowcoder
leetcode

题目描述

给定一个数组 A[0,1,…,n-1]，请构建一个数组 B[0,1,…,n-1]，
其中 B[i] = A[0]A[1]...A[i-1]*A[i+1]...*A[n-1]，不能使用除法。
规定： B[0] = A[1]A[2]*...*A[n-1], B[n-1] = A[0]A[1]*...*A[n-2]

C++ 代码 - nowcoder

/*
    B[i] = (A[0]A[1]...A[i-1]) * (A[i+1]...*A[n-2]*A[n-1])
         = C[i] * D[i]
    
    C[i] = C[i-1] * A[i-1]
    D[i] = D[i+1] * A[i+1]
    
    时间复杂度：O(n)
    空间复杂度：O(1)
*/
class Solution {
public:
    vector<int> multiply(vector<int>& A) {
        if (A.size() <= 1) return vector<int>{};

        int length = A.size();
        vector<int> B(length, 0);
        B[0] = 1;
        for (int i = 1; i < length; i ++) {
            B[i] = B[i - 1] * A[i - 1]; 
        }

        int temp = 1;
        for (int i = length - 2; i >= 0; i --) {
            temp = temp * A[i + 1];
            B[i] = B[i] * temp;
        }

        return B;
        // return std::move(B);
    }
};

C++ 代码 - leetcode

/*
	索引左侧所有数字的乘积 * 索引右侧所有数字的乘积（即前缀与后缀），相乘得到答案。
	
	时间复杂度：O(n)
	空间复杂度：O(n)
*/
class Solution {
public:
    vector<int> statisticalResult(vector<int>& nums) {
        int n = nums.size();
        if (n == 0) return vector<int>{};

        // 从左到右的前缀积，prefix[i] 是 nums[0..i] 的元素积
        vector<int> prefix(n);
        prefix[0] = nums[0];
        for (int i = 1; i < n; i++) {
            prefix[i] = prefix[i - 1] * nums[i];
        }
        // 从右到左的后缀积，suffix[i] 是 nums[i..n-1] 的元素积
        vector<int> suffix(n);
        suffix[n - 1] = nums[n - 1];
        for (int i = n - 2; i >= 0; i--) {
            suffix[i] = suffix[i + 1] * nums[i];
        }

        // 结果数组
        vector<int> res(n);
        res[0] = suffix[1];
        res[n - 1] = prefix[n - 2];
        for (int i = 1; i <= n - 2; i++) {
            // 结果是 nums[i] 左侧和右侧所有元素之积
            res[i] = prefix[i - 1] * suffix[i + 1];
        }
        return res;
    }
};

/*    
    时间复杂度：O(n)
    空间复杂度：O(1)
*/
class Solution {
public:
    vector<int> statisticalResult(vector<int>& arrayA) {
        int length = arrayA.size();
        if (length == 0) return vector<int>{};

        vector<int> arrayB(length, 0);
        arrayB[0] = 1;
        for (int i = 1; i < length; i ++) {
            arrayB[i] = arrayB[i - 1] * arrayA[i - 1]; 
        }

        int temp = 1;
        for (int i = length - 2; i >= 0; i --) {
            temp = temp * arrayA[i + 1];
            arrayB[i] = arrayB[i] * temp;
        }

        return arrayB;
    }
};