LeetCode_238_Product of Array Ex

Given an array of n integers where n > 1, nums, return an array output such that output[i] is equal to the product of all the elements of nums except nums[i].
Solve it without division and in O(n).
For example, given [1,2,3,4], return [24,12,8,6].
Follow up:
Could you solve it with constant space complexity? (Note: The output array does not count as extra space for the purpose of space complexity analysis.)

题目分析：

给定一个num数组，n>1，输出一个output数组，且output[i]等于除num[i]之外所有元素的乘积，给出一个满足一下条件的solution:

• 不使用除法
• 时间复杂度O(n)
• 不使用额外的储存空间（输出数组不算）

解
假定
s1[0] = nums[0];
s2[n] = nums[n];
构建以下数组
s1[i] = nums[0]*nums[1]*nums[i];
s2[i] = nums[n]*nums[n-1]*...*nums[i];
则可知
output[i] =s1[i-1]*s2[i+1]
其中：
s1[i- 1] = nums[0] * nums[1]*...nums[i-1]
s2[i+1] = nums[i+1]* nums[i+2]* ... nums[n]

Solution1

vector<int> productExceptSelf(vector<int>& nums) {
    int n = nums.size()-1;
    vector<int> vS1(n+1),vS2(n+1);
    vector<int> vRst(n+1);
    int result_s = 1,result_e = 1;  
    for(int i = 1; i<= n; i++)
        result_s *= nums[i];
    vRst[0] = result_s; 
    for(int i = 0; i< n; i++)
        result_e *= nums[i];
    vRst[n] = result_e;
    vS1[0] = nums[0];
    vS2[n] = nums[n];   
    for(int i = 1; i<= n; i++)
    {
        vS1[i] = vS1[i-1] * nums[i];　　//由于vS1[0]已知,从vS1[1]开始计算
        vS2[n-i] = vS2[n-i+1] * nums[n-i];　　//由于vS2[n]已知,从vS2[n-1]开始计算
    }   
    for(int i =1; i< n; i++)
    {
        vRst[i] = vS1[i-1] * vS2[i+1];
    }
    return vRst;
}

分析两个for循环可知：

1. 在第i次循环时，vS1[i-1]是已知的，且vRst[i]的值不会对vS2[i+1]造成影响。

2. 所以可将vS1[i-1]用一个int类型变量保存，vS2[i+1]的值则保存为vRst[i+1],以满足题目中不开辟额外空间的要求。

给出以下

Solution2

vector<int> productExceptSelf(vector<int>& nums) {
    int n = nums.size()-1;
    vector<int> vRst(n+1);
    int result_s = 1;
    
    int s1 = nums[0];
    vRst[n] = nums[n];
    
    for(int i= 1; i<=n; i++)
        vRst[n-i] = vRst[n-i+1] * nums[n-i];
    vRst[0] = vRst[1];
    
    for(int i =1; i<n;i++)
    {
        vRst[i] = s1 *vRst[i+1];
        s1 *= nums[i];
    }

    vRst[n] = s1;
    return vRst;
}

最后是LeetCode Discuss中大犇 给出的答案，比Solution2更快（虽然3个solution Tn = O(n)）

Solution3

vector<int> productExceptSelf(vector<int>& nums) {
    int n=nums.size();
    int fromBegin=1;
    int fromLast=1;
    vector<int> res(n,1);

    for(int i=0;i<n;i++){
        res[i]*=fromBegin;
        fromBegin*=nums[i];
        res[n-1-i]*=fromLast;
        fromLast*=nums[n-1-i];
    }
    return res;
}