【LeetCode】 238. Product of Array Except Self

Description

Given an array nums of n integers where n > 1, return an array output such that output[i] is equal to the product of all the elements of nums except nums[i].

Constraint: It's guaranteed that the product of the elements of any prefix or suffix of the array (including the whole array) fits in a 32 bit integer.

Note: Please solve it without division and in O(n).

Follow up:
Could you solve it with constant space complexity? (The output array does not count as extra space for the purpose of space complexity analysis.)

給予有n個整數的陣列nums且n > 1，回傳一個陣列output且output[i]等於nums所有元素的乘積除了nums[i]。

制約：保證乘積一定在32位元的表示範圍之內。

注意：請不使用除法並且在O(n)的時間複雜度之下完成此題。

進階：
你可以在常數等級的空間複雜度完成這題嗎？（output陣列並不算在額外空間之中。）

Example:

Example:

Input:  [1,2,3,4]
Output: [24,12,8,6]

Solution

• 如果沒有除法的限制，這題就很簡單：
  • 先算出所有元素的乘積，然後跑一次for將元素除回去即可。
  • 但這樣這題就不會是中等難度了XD
• 不使用除法的情況之下，我們可以先想想，不乘上自己的話，就是自己前面的乘積 * 自己後面的乘積。
• 因此我們就跑兩次for，分別得到前面和後面的乘積，最後再一個for相乘即可得到答案。
  • 時間複雜度O(3n) = O(n)。

---

• 挑戰的部分怎麼做呢？其實很簡單，仔細觀察後就會發現，back和front其實只需要其中一個，另一個的運算可以直接跟原本的nums結合就好。
  • 在下方範例中保留back。
  • 詳細的部分就請直接看下方code自己trace了。

Code

• 一般

class Solution {
public:
    vector<int> productExceptSelf(vector<int>& nums) {
        vector<int> front(nums.size(), 1), back(nums.size(), 1);
        for(int i = 1; i < nums.size(); i++)
            back[i] = back[i - 1] * nums[i - 1];
        for(int i = nums.size() - 2; i >= 0; i--)
            front[i] = front[i + 1] * nums[i + 1];
        for(int i = 0; i < nums.size(); i++)
            nums[i] = front[i] * back[i];
        return nums;
    }
};

• 挑戰

class Solution {
public:
    vector<int> productExceptSelf(vector<int>& nums) {
        vector<int> back(nums.size(), 1);
        for(int i = 1; i < nums.size(); i++)
            back[i] = back[i - 1] * nums[i - 1];
        int temp = 1;
        nums.push_back(1);
        for(int i = back.size() - 1; i >= 0; i--)
        {
            temp *= nums[i + 1];
            back[i] *= temp;
        }
        return back;
    }
};

tags: LeetCode C++