题目

题解

两个方法，其实本质是一个，第二个是第一个优化空间复杂度

1. 左右分开动态规划(双数组)

其实就是dp左右两边的数组，左边的从1开始到n-1，右边的从n-2开始到0。然后再乘起来就可以。两个数组的起始值都初始化为1。

  • 时间复杂度$O(n)$
  • 空间复杂度$O(n)$
class Solution {//两个方法。1.左右分开动态规划(双数组)
public:
    vector<int> constructArr(vector<int>& a) {
        const int n = a.size();
        if(n == 0) return a;
        vector<int> left(n);//左边的乘积数组
        vector<int> right(n);//右边的乘积数组
        vector<int> b(n);//结果
        left[0] = 1;
        right[n-1] = 1;//初始化，边界上的两个的最左（或最右）数组均为1（即不乘任何一个数）
        //计算左数组，注意是乘a[i-1]，注意边界时[1,n-1]（跳过第一个）
        for(int i = 1; i < n; ++i){
            left[i] = left[i-1] * a[i - 1];
        }
        //计算右数组，注意是乘a[i+1]，注意边界时[n-2,0]（跳过最后一个）
        for(int i = n-2; i >= 0; --i){
            right[i] = right[i+1] * a[i + 1];
        }
        //然后把左右数组乘起来就可以了
        for(int i = 0; i < n; ++i){
            b[i] = left[i] * right[i];
        }
        return b;
    }
};

2. 左右合起来动态规划(单数组)

这个就是上一个方法的优化，只有一个数组并直接返回。先从上到下dp左数组，再用辅助变量tmp直接乘上右数组的值，最后直接返回。

  • 时间复杂度$O(n)$
  • 空间复杂度$O(1)$
class Solution {//两个方法。2. 左右合起来动态规划(单数组)
public:
    vector<int> constructArr(vector<int>& a) {
        const int n = a.size();
        if(n == 0) return a;
        vector<int> b(n);//结果
        b[0] = 1;
        int tmp = 1;
        //计算左数组，注意是乘a[i-1]，注意边界时[1,n-1]（跳过第一个）
        //和方法1的第一个循环完全相同
        for(int i = 1; i < n; ++i){
            b[i] = b[i-1] * a[i - 1];
        }
        //计算右数组，注意是乘a[i+1]，注意边界时[n-2,0]（跳过最后一个）
        for(int i = n-2; i >= 0; --i){
            tmp = tmp * a[i + 1];//对应方法1的第二个循环
            b[i] = tmp * b[i];//对应方法1的第三个循环
        }
        return b;
    }
};