We love coding - #2

Hi, I'm coding dog. We love coding.

Here's today's coding interview problem.

Q:

給定一個整數陣列，請回傳一個新的陣列，其中新陣列中的每個索引 i 的元素都是原始陣列中除了索引 i 的所有數字的乘積。

例如，如果我們的輸入是 [1, 2, 3, 4, 5]，則預期輸出為 [120, 60, 40, 30, 24]。如果我們的輸入是 [3, 2, 1]，則預期輸出為 [2, 3, 6]。不使用除法。

A:

解決這個問題，我們可以先計算出陣列中所有元素的乘積。然後，對於陣列中的每個元素，我們可以將總乘積除以該元素，以獲得其他元素的乘積。我們可以使用一個新的陣列來存儲這些乘積。

以下是這個方法的 Python 代碼：

def product_except_self(nums):
    product = 1
    for num in nums:
        product *= num
    result = []
    for num in nums:
        result.append(product // num)
    return result

這個方法的時間複雜度為 O(n)，其中 n 是輸入陣列的長度。但是，如果輸入陣列中有零，就可能會出現除以零的問題。

要處理不能使用除法的情況，我們可以使用兩個陣列：一個用於存儲每個元素左側所有元素的乘積，另一個用於存儲每個元素右側所有元素的乘積。然後，我們可以結合這兩個陣列來獲得最終結果。

以下是這個方法的 Python 代碼：

def product_except_self(nums):
    n = len(nums)
    left_products = [1] * n
    right_products = [1] * n
    for i in range(1, n):
        left_products[i] = left_products[i-1] * nums[i-1]
    for i in range(n-2, -1, -1):
        right_products[i] = right_products[i+1] * nums[i+1]
    result = [left_products[i] * right_products[i] for i in range(n)]
    return result

這個方法的時間複雜度為 O(n)，其中 n 是輸入陣列的長度。這個方法不會出現上一個方法中的除以零問題。