构建乘积数组（C++）_c++对数组内元素全部乘以一个数

构建乘积数组

描述

  给定一个数组 A[0,1,…,n-1] ,请构建一个数组 B[0,1,…,n-1] ,其中 B 的元素 B[i]=A[0]*A[1]*…*A[i-1]*A[i+1]*…*A[n-1]（除 A[i] 以外的全部元素的的乘积）。程序中不能使用除法。（注意：规定 B[0] = A[1] * A[2] * … * A[n-1]，B[n-1] = A[0] * A[1] * … * A[n-2]）

对于 A 长度为 1 的情况，B 无意义，故而无法构建，用例中不包括这种情况。

数据范围：1≤n≤10 ，数组中元素满足∣val∣≤10

实例1

输入：
[1,2,3,4,5]
返回值：
[120,60,40,30,24]
1
2
3
4

实例2

输入：
[100,50]
返回值：
[50,100]
1
2
3
4

思路/解法

方式一

暴力穷举即可求得。

class Solution {
public:
    vector<int> multiply(const vector<int>& A) {
        vector<int> res;
        for(int i = 0;i<A.size();i++)
        {
            int sum = 1;
            for(int j = 0;j<A.size();j++)
            {
                if(j != i)
                    sum *= A[j];
            }
            res.push_back(sum);
        }
        return res;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

方式二

进行简单的优化，当前位置前面数的乘积使用一个临时空间记录。这样可以保证当前数前面的乘积无需计算，以下的时间复杂度仍然过高，可以使用一次O(n)的循环先求得临时空间，然后再使用一次O(n)的效率求得最终乘积

class Solution {
public:
    vector<int> multiply(const vector<int>& A) {
        vector<int> res;
        vector<int> visited(A.size());//临时空间
        for(int i = 0;i<A.size();i++)
        {
            if(i == 0)
                visited[0] = 1;
            else if(i == 1)
                visited[1] = A[0];
            else
                visited[i] = visited[i-1]*A[i-1];
            int sum = visited[i];
            for(int j = i+1;j < A.size();j++)
                sum *= A[j];
            res.push_back(sum);
        }
        return res;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21