2023-03-08|閱讀時間 ‧ 約 3 分鐘

We love coding - #2

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

Here's today's coding interview problem.

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

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

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

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

分享至

成為作者繼續創作的動力吧！

從 Google News 追蹤更多 vocus 的最新精選內容

作者的相關文章

成為會員後即可發表留言