演算法練習 Leetcode 力扣 238. Product of Array Except Self解法

解法1, 用一個list記錄從左邊開始除了自己的乘積,然後另一個list記錄右邊開始除了自己的乘積,然後把這輛list對應項乘起來就行。實際實現的時候右邊的list可以用一個數代替節省一點空間

例子 1,沒有0的情況

例子 2,有0的情況

思路其實和盛水題目有點像

時間 O(N),空間 O(N)

Python代碼

class Solution:
    # @param {integer[]} nums
    # @return {integer[]}
    def productExceptSelf(self, nums):
        l = len(nums)
        ret = [1] * l
        for i in range(1, l):
            ret[i] = ret[i-1] * nums[i-1]
        right = 1
        for i in range(l-2, -1, -1):
            right *= nums[i+1]
            ret[i] *= right
        return ret
            

解法2,根據0的情況分類。

如果沒0,全部乘起來,然後再掃一遍,除以自己。
有一個0,把非0的乘起來,除了0的位置,其他全是0, 0的位置為其他非0的乘積。
有2個及以上的0,全部都是0

例子

時間 O(N),空間 O(N)

Python

class Solution(object):
    def productExceptSelf(self, nums): 
        """
        :type nums: List[int]
        :rtype: List[int]
        """
        product = None
        zero_index = None
        zero_counts = 0
        for i in xrange(len(nums)):
            if product is None:
                product = nums[i]
                continue
            
            if nums[i] != 0:
                product *= nums[i]
            else:
                zero_counts += 1
                zero_index = i
            
            if zero_counts == 2:
                break
        
        if product is None:
            return product
        
        if zero_counts == 0:
            products = [product / x for x in nums]
        elif zero_counts == 1:
            products = [0] * len(nums)
            products[zero_index] = product
        else:
            products = [0] * len(nums)
        return products

做這題想到這倆解法相隔竟已5年。

Leave a Comment

Your email address will not be published.