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 是輸入陣列的長度。這個方法不會出現上一個方法中的除以零問題。