We love coding - #2
2023/03/08閱讀時間約 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 = 1for num in nums:product *= numresult = []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] * nright_products = [1] * nfor 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 是輸入陣列的長度。這個方法不會出現上一個方法中的除以零問題。
留言0
查看全部