C++刷剑指offer（面试题66. 构建乘积数组）【数据结构】

糖逗

在线题目：leetcode
题目描述：

1. 给定一个数组 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]。不能使用除法。
   
2. 
   
3.  
   
4. 
   
5. 示例:
   
6. 
   
7. 输入: [1,2,3,4,5]
   
8. 输出: [120,60,40,30,24]
   
9.  
   
10. 
    
11. 提示：
    
12. 
    
13. 所有元素乘积之和不会溢出 32 位整数
    
14. a.length <= 100000
    
15. 
    

复制代码

1. #include <iostream>
   
2. #include <vector>
   
3. 
   
4. using namespace std;
   
5. 
   
6. 
   
7. vector<int> solution(vector<int> input){
   
8.         int size = input.size();
   
9.         vector<int> result(size, 1);
   
10.         int left = 1;
    
11.         for(int i = 0; i < input.size(); i++){
    
12.                 result[i] = left;
    
13.                 left *= input[i];       
    
14.         }
    
15.         int right = 1;
    
16.         for(int i = input.size() - 1; i >= 0; i--){
    
17.                 result[i] *= right;
    
18.                 right *= input[i];
    
19.                
    
20.         }
    
21.         return result;
    
22. }
    
23. 
    
24. int main(void){
    
25.         int number;
    
26.         vector<int> input;
    
27.         while(cin >> number){
    
28.                 input.push_back(number);
    
29.         }
    
30.        
    
31.         vector<int> result;
    
32.         result = solution(input);
    
33.         for(int i = 0; i < result.size(); i++){
    
34.                 cout << result[i] << " ";
    
35.         }
    
36.         cout << endl;
    
37.         return 0;
    
38. }

复制代码

糖逗