Leetcode 238. Product of Array Except Self

給定一個整數數組 nums，返回一個數組 answer，使得 answer[i] 等於 nums 除 nums[i] 之外的所有元素的乘積。O(n) 時間複雜度下

Python

先從左邊開始，得到左邊的乘積，再從右邊回來，把先前算出的乘積們，乘上從右邊回來的乘積。

class Solution:
  def productExceptSelf(self, nums: List[int]) -> List[int]:
    n = len(nums)
    prefix = [1] * n  # Prefix product
    suffix = [1] * n  # Suffix product

    for i in range(1, n):
      prefix[i] = prefix[i - 1] * nums[i - 1]

    for i in reversed(range(n - 1)):
      suffix[i] = suffix[i + 1] * nums[i + 1]

    return [prefix[i] * suffix[i] for i in range(n)]

參考:https://englishandcoding.pixnet.net/blog/post/34138027-leetcode-%E7%AD%86%E8%A8%98%EF%BC%8D238.-product-of-array-except-self

class Solution:
  def productExceptSelf(self, nums: List[int]) -> List[int]:
    n = len(nums)
    ans = [1] * n


    for i in range(1, n):
      ans[i] = ans[i - 1] * nums[i - 1]

    suffix = 1  
    for i, num in reversed(list(enumerate(nums))):
      ans[i] *= suffix
      suffix *= num

    return ans

C++

1.定義輸出數組：

定義一個長度為n的輸出數組output，其中每個元素初始值為1。

2.計算左側乘積：

從左往右遍歷數組nums，在遍歷到第i個元素時，將output[i]乘以其左側元素的乘積left，並將left更新為left乘以nums[i]的值。

3.計算右側乘積：

從右往左遍歷數組nums，在遍歷到第i個元素時，將output[i]乘以其右側元素的乘積right，並將right更新為right乘以nums[i]的值。

4.返回輸出數組：

返回輸出數組output。

時間複雜度：O(n)，其中n為數組的長度。需要遍歷數組兩次，因此時間複雜度為O(n)。

空間複雜度：O(1)，除了輸出數組外，沒有使用額外的空間，因此空間複雜度為O(1)。

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

Python

C++

相關