[leet_code] 238. Product of Array Except Self

Array Product of Except Selfの問題

Given an integer array nums, return an array answer such that answer[i] is equal to the product of all the elements of nums except nums[i].
The product of any prefix or suffix of nums is guaranteed to fit in a 32-bit integer.
You must write an algorithm that runs in O(n) time and without using the division operation.
Example 1:
Input: nums = [1,2,3,4]
Output: [24,12,8,6]
Example 2:
Input: nums = [-1,1,0,-3,3]
Output: [0,0,9,0,0]
Constraints:
2 <= nums.length <= 105
-30 <= nums[i] <= 30
The product of any prefix or suffix of nums is guaranteed to fit in a 32-bit integer.
Follow up: Can you solve the problem in O(1) extra space complexity? (The output array does not count as extra space for space complexity analysis.)

よく問題を見なければならない。

You must write an algorithm that runs in O(n) time and without using the division operation.条件は、以下のコードを作成したことです.

class Solution:
    def productExceptSelf(self, nums: List[int]) -> List[int]:
        num_product = 1
        cnt = 0
        answer = []
        for i in nums:
            if i != 0:
                num_product *= i
            if i == 0:
                cnt += 1
        
        if cnt >= 2:
            answer = [0] * len(nums)
            return answer
        
        for i in nums:
            if cnt == 1:
                if i == 0:
                    answer.append(num_product)
                else:
                    answer.append(0)
                
            else:
                answer.append(num_product // i)
                
        return answer

上のコードは時間の複雑さを守っていますが、問題の条件に違反しています.つまり、除算を書かないでください.

解決策

num=[a,b,c,d,e].(すべて整数です.)
では,resolution=[bcde,acde,abde,abce,abcd]のアルゴリズムを構築する必要がある.
よく見ると、ある転換点からその文字を分割できるようです.
[|bcde,a|cde,abc|e,abcd|]では、いくつかのルールが表示されます.
では[1,a,ab,abc,abcd],[bcde,cde,de,e,1]の2つのリストを元素で乗算すれば解決済みと考えられる.

class Solution:
    def productExceptSelf(self, nums: List[int]) -> List[int]:
        res = []
        left_list = [1]
        right_list = [1]
        
        ### left part
        temp = 1
        for left in nums:
            temp = temp * left
            left_list.append(temp)
        
        else:
            left_list.pop()
        
        ### right part 
        temp = 1
        for right in nums[::-1]:
            temp = temp * right
            right_list.append(temp)
            
        else:
            right_list.pop()
            right_list = right_list[::-1]
            
        
        for left, right in zip(left_list, right_list):
            res.append(left * right)
        
        return res
    

スペースの複雑さをさらに低減できます。

class Solution:
    def productExceptSelf(self, nums: List[int]) -> List[int]:
        res = []
        
        p = 1
        for i in range(len(nums)):
            res.append(p)
            p = p * nums[i]
        
        p = 1
        for i in range(len(nums) - 1, -1, -1):
            res[i] = res[i] * p #1
            p = p*nums[i]
        
        return res

このアルゴリズムの順序

[1]、a、ab、abc、abcd]を使用してリストを作成する
[1, a, ab, abc, abcd] > [1, a, ab, abce, abcd] > [1, a, abde, abce, abcd] >
[1, acde, abde, abce, abcd] > [bcde, acde, abde, abce, abcd]
resという名前のリストのみが使用され、使用空間が最小化されます.