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

[utterances-bot]

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

238. 除自身以外数组的乘积 # 标签：数组 难度：中等 题目大意 # 给定一个数组 nums。要求输出数组 output，其中 output[i] 为数组 nums 中除了 nums[i] 之外的其他所有元

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.)

即不包括输出的数组