LeetCode_Array_238. Product of Array Except Self 除自身以外數組的乘積（C++/Java）

目錄

一，題目描述

英文描述

中文描述

二，解題思路

三，AC代碼

C++

Java

四，解題過程

第一博

第二搏

第三搏

一，題目描述

原題連結238. 除自身以外數組的乘積

英文描述

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

Example:

Input:  [1,2,3,4]

Output: [24,12,8,6]

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] 之外其餘各元素的乘積。

示例:

輸入: [1,2,3,4]

輸出: [24,12,8,6]

提示：題目資料保證數組之中任意元素的全部字首元素和字尾（甚至是整個數組）的乘積都在 32 位整數範圍内。

說明: 請不要使用除法，且在 O(n) 時間複雜度内完成此題。

進階：

你可以在常數空間複雜度内完成這個題目嗎？（ 出于對空間複雜度分析的目的，輸出數組不被視為額外空間。）

來源：力扣（LeetCode）

連結：https://leetcode-cn.com/problems/product-of-array-except-self

著作權歸領扣網絡所有。商業轉載請聯系官方授權，非商業轉載請注明出處。

二，解題思路

ans數組存放最終答案，left記錄目前位置左邊元素之積，right記錄目前位置右邊元素之積；

以上變量全部初始為1；

周遊數組一次，每次循環将ans中相應位置分别乘以 left 和 right （ans[i] *= left ；ans[j] *= right;），并更新left和right（left *= nums[i] ； right *= nums[j]）；

三，AC代碼

C++

class Solution {
public:
    vector<int> productExceptSelf(vector<int>& nums) {
        vector<int> ans(nums.size(), 1);
        int n = nums.size(), left = 1, right = 1;
        for(int i = 0, j = n - 1; i < n; i++, j--) {
            ans[i] *= left;
            left *= nums[i];

            ans[j] *= right;
            right *= nums[j];
        }
        return ans;
    }
};
           

Java

class Solution {
    public int[] productExceptSelf(int[] nums) {
        int[] ans = new int[nums.length];
        int n = nums.length, left = 1, right = 1;
        for(int i = 0; i < n; i++) ans[i] = 1;
        for(int i = 0, j = n - 1; i < n; i++, j--) {
            ans[i] *= left;
            left *= nums[i];

            ans[j] *= right;
            right *= nums[j];
        }
        return ans;
    }
}
           

四，解題過程

第一博

三次周遊數組。

• 從左向右周遊，ans[i]記錄目前元素左邊所有元素之積；
• 從右向左周遊，tem[i]記錄目前元素右邊所有元素之積；
• 最後周遊一次，将兩個數組對應位置元素相乘即可ans[i] = ans[i] * tem[i]；

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

慘不忍睹的效率：時間O(N)，空間O(N)

第二搏

兩次周遊數組；

• 從左向右周遊，ans[i]記錄目前元素左邊所有元素之積；
• 從右向左周遊，tem記錄目前元素nums[i]右邊所有元素之積，更新ans[i] *= tem; tem *= nums[i]；

這樣時間為O(N)，空間O(1)（按照題目說明，答案的數組不算做占用的空間）

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

然鵝o(￣┰￣*)ゞ

第三搏

思路受到局限了，既然從右到左累乘結果可以用一個變量代替，那麼從左到右為什麼不能？

為什麼要按照順序累乘，先從左到右乘一遍，再從右到左乘一遍？左右同時開工不香嗎？

class Solution {
public:
    vector<int> productExceptSelf(vector<int>& nums) {
        vector<int> ans(nums.size(), 1);
        int n = nums.size(), left = 1, right = 1;
        for(int i = 0, j = n - 1; i < n; i++, j--) {
            ans[i] *= left;
            left *= nums[i];

            ans[j] *= right;
            right *= nums[j];
        }
        return ans;
    }
};
           

然鵝，難以置信耗時居然還變多了o(￣┰￣*)ゞ