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, ab|de, abc|e, abcd|] 이제야 규칙이 조금 보인다.
그렇다면 [1, a, ab, abc, abcd] , [bcde, cde, de, e, 1] 이 두 리스트를 element wise하게 곱해주면 해결이 완료 된다고 볼 수 있다.
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 라는 하나의 리스트만을 사용해 사용공간을 최소화 하였다.