leetcode-238-Product-of-Array-Except-Self

发表于   |  

描述

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.)

分析

题目意思就是说有一个数组，例如[a1, a2, a3, a4]，需要返回[a2*a3*a4, a1*a3*a4, a1*a2*a4, a1*a2*a3]，题目要求不能用除法解决，空间复杂度为常数。解决方法：[a2*a3*a4, a1*a3*a4, a1*a2*a4, a1*a2*a3]可以表示为[1, a1, a1*a2, a1*a2*a3] 与 [a2*a3*a4, a3*a4, a4, 1]相乘，用两个循环构造即可，复杂度为$O(n)$

解决方案1(C++)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
    vector<int> productExceptSelf(vector<int>& nums) {
        int len = nums.size();
        vector<int> result(len, 1);
        int now = 1;
        
        for(int i = 1; i < len; i++) {
            now *= nums[i-1];
            result[i] = now;
        }
        
        now = 1;
        for(int i = len-2; i >= 0; i--) {
            now *= nums[i+1];
            result[i] *= now;
        }
        
        return result;
    }
};

相关问题

(H) Trapping Rain Water
(H) Paint House II
(M) Maximum Product Subarray

题目来源