leetcode筆記：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.)

二. 題目分析

該題的大意是，給定一個整數數組，讓我們返回一個新數組，對於新數組中每一個位置上的數，是原始數組其他位置上的數的乘積。題目限定了時間復雜度：O(n)，而且對空間復雜度也有要求。

一開始隨便寫了一段，果斷超時了。

後面換了一個思路。先從前到後遍歷數組nums，一個數組result用於存儲的是除了當前元素外的所有前面元素的乘積；然後，再從後到前遍歷nums，同樣用result累積除了當前元素外的所有後面元素的乘積。

這樣做，實際上可簡化為一次遍歷，即可完成整個工作。

三. 示例代碼

// 超時
class Solution {
public:
    vector productExceptSelf(vector& nums) {
        int SIZE = nums.size();
        vector result(SIZE);
        for (int i = 0; i < SIZE; ++i)
        {
            int temp = 1;
            for (int j = 0; j < i; ++j)
                temp *= nums[j];
            for (int k = i + 1; k < SIZE; ++k)
                temp *= nums[k];

            result[i] = temp;
        }
        return result;
    }
};

// 一遍掃描，AC
class Solution {
public:
    vector productExceptSelf(vector& nums) {
        int SIZE = nums.size();
        int left = 1, right = 1;
        vector result(SIZE, 1);
        for (int i = 0; i < SIZE; ++i)
        {
            result[i] *= left;
            left *= nums[i];
            result[SIZE - 1 - i] *= right;
            right *= nums[SIZE - 1 - i];
        }
        return result;
    }
};

四. 小結

使用類似思路的題目很多，在一些時候可以減少不必要的迭代運算，需要多加練習。