0238. 除自身以外数组的乘积

[utterances-bot]

0238. 除自身以外数组的乘积 | 算法通关手册

https://algo.itcharge.cn/solutions/0200-0299/product-of-array-except-self/

[weibaozi]

自己写了个,更快一点,理论上要计算一次全部数相乘后再算n次除法就好

class Solution:
    def productExceptSelf(self, nums: List[int]) -> List[int]:
        result=[0]*len(nums)
        mul_sum=1  # multiply sum
        num_zero=0 # number of zeros occurs in nums
        zero_index=0 #index of zero, just need record the first occurrence
        for i in range(len(nums)):
            #if nums[i] is 0, record index, skip this cycle ignore 0 on mul_sum
            if (nums[i] == 0):
                zero_index=i
                num_zero+=1
                # if there are more than two 0 break and result list keep all zero
                if (num_zero == 2):
                    break
                continue
            mul_sum *= nums[i]
        #if there is only one 0 num. others keep 0 except the 0 num, and the 0 num
        if (num_zero == 1):
            result[zero_index]=mul_sum
        elif (num_zero == 2):
            pass
        #else go over list, divide mul_sum by itself
        else:
            for i in range(len(nums)):
                result[i]=mul_sum//nums[i]
        return result

[AndrewGuo0930]

题目中写了不能用除法

[weibaozi]

class Solution:
    def productExceptSelf(self, nums: List[int]) -> List[int]:
        result=[0]*len(nums)
        mul_sum=1  # multiply sum
        num_zero=0 # number of zeros occurs in nums
        zero_index=0 #index of zero, just need record the first occurrence
        for i in range(len(nums)):
            #if nums[i] is 0, record index, skip this cycle ignore 0 on mul_sum
            if (nums[i] == 0):
                zero_index=i
                num_zero+=1
                # if there are more than two 0 break and result list keep all zero
                if (num_zero == 2):
                    break
                continue
            mul_sum *= nums[i]
        #if there is only one 0 num. others keep 0 except the 0 num, and the 0 num
        if (num_zero == 1):
            result[zero_index]=mul_sum
        elif (num_zero == 2):
            pass
        #else go over list, divide mul_sum by itself
        else:
            for i in range(len(nums)):
                result[i]=mul_sum//nums[i]
        return result

刚才markdown格式有问题再发一下

[changxu001]

        res[i] *= left

感觉这里直接写 = 就好了， = 让人想了一会 1left就是1

[CtaKing]

res = [1 for _ in range(size)]

空间复杂度不是O(n)了吗？

[AndrewGuo0930]

题目中写的是

Can you solve the problem in O(1) extra space complexity? (The output array does not count as extra space for space complexity analysis.)

即不包括输出的数组