LeetCode 238: Product of Array Except Self

Difficulty: Medium

Tags: Array

问题描述

给定一个有 n 个整型数的数组 nums，返回一个数组 output，output[i]的值等于 nums 中除了 nums[i] 外其他所有元素的乘积。

本题要求不能使用除法以及时间复杂度为 O(n)。

解决方案

output[i] 就是 nums[i] 在 nums 数组中 前面所有元素乘积 与 后面所有元素乘积 的乘积。

那么就可以用2个数组来分别存储 nums 顺序各位乘积 和 逆序各位乘积。

因为 output[i] 的计算过程中总是会用到 n-1 个元素，所以用一个迭代器扫一遍就可以控制 output[i] 的计算了。

▷ Time Complexity: O(n)

▷ Space Complexity: O(n)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution {
public:
    vector<int> productExceptSelf(vector<int>& nums) {
        int size = nums.size();
        
        vector<int> res(size);
        vector<int> begin(size);    // 顺序
        vector<int> end(size);      // 逆序
        
        begin[0] = 1;
        end[0] = 1;
        
        for(int i=1; i<size; i++)
        {
            begin[i] = begin[i-1]*nums[i-1];
            end[i] = end[i-1]*nums[size-i];
        }
        
        for(int j=0; j<size; j++)
        {
            res[j] = begin[j]*end[size-j-1];
        }
        
        return res;
    }
};

回到 Conquer Leetcode