【LeetCode】238. Product of Array Except Self 解答・解説【Python】

はじめに
詳細
終わりに
1. 補足・参考・感想
2. 他の問題もどうぞ

はじめに

LeetCodeの問題を解答します。

なるべく、問題の和訳と詳細なコメントを書いています。

余裕があれば、複数のアプローチの解答と、実際の面接を想定して英語での解法やコメントを書いています。

これまでこのサイトでメモしてきた問題はこのページに全て載せています。

LeetCode 解答・解説記事一覧

二分探索、連結リストなど、テーマを絞って集中的に解きたい方は以下の記事が有用です。

LeeetCodeの問題をアルゴリズムとデータ構造による分類しました。

また、LeetCodeではAtcoderと違ってクラスと関数を定義して解答します。

LeetCodeに特有の内容など、知っておくと役に立つかもしれないことをまとめています。

はじめてLeetCodeに触れる方はこちらの記事も役に立つと思います。

解答前に知っておくと役に立つかもしれない情報

詳細

問題

原文

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]

1
2

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]

1
2

Input: nums = [-1,1,0,-3,3]
Output: [0,0,9,0,0]

Constraints:

2 <= nums.length <= 10⁵

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

内容(和訳)

整数配列numsが与えられます。i番目の要素がそれ以外の全要素の掛算である配列を返してください。任意のnumsの接頭辞または接尾辞の積は、32ビット整数に収まることが保証されています。

O(n)の時間内に動作し、除算演算を使用しないアルゴリズムを書く必要があります。

※正しくない可能性があります。

考察

2重ループで掛算をするとシンプルでわかりやすいですが、問題の指定にあるO(n)の時間計算量には収まりません。O(n)で解答するには、最初に全ての掛算をしておき、後から各要素ごとに割り算した値を解答用のリストに保存しておく必要があります。

ただし、0が含まれている場合の扱いに注意が必要です。

0が2つあれば、全ての要素は0を持つリストを返せばよく、0が一つだけの場合は、それ以外の要素は0、0の時だけはそれ以外の全要素の掛算の結果を解答として返す必要があります。

[1,2,0,3]の場合→[0,0,6,0]が解答

[1,0,0,4]の場合→[0,0,0,0]が解答

以下は英語面接をイメージして記載していたコメントです。

“””

About question

I need to answer the array.

The array has element that has the result of product of all element except i-th element.

Assumption

1.Length of nums is at least one

2.nums is from -100 to 100

Test cases

1.general

[1,2,3,4]

[24,12,8,6]

2.general

[0,-1,4,9,-45]

[]

3.edge case

[1]

[]

4.edge case

[0,0,0]

[0,0,0]

Approach

1.Brute Force

1.Perfome for loop iterate over each element.

2.product all elements except i-th element

Time complexity is Big O of n^2.

Space complexity is Big O of n.

2.

1.calculate product of each element

2.Performe for loop.

each iterate the result of all elements is divided by i-th element

and append to the array to return.

3.Return the array.

Time complexity is Big O of n.

Space complexity is Big O of n.

“””

解答

解答1：Brute Force

1.Brurte Force
class Solution:
    def productExceptSelf(self, nums: List[int]) -> List[int]:
        answer = []
        for i in range(len(nums)):
            product = 1
            for j in range(len(nums)):
                if i!=j:
                    product *= nums[j]
            answer.append(product)
        return answer

1.Brurte Force

class Solution:

def productExceptSelf(self, nums: List[int]) -> List[int]:

answer = []

for i in range(len(nums)):

product = 1

for j in range(len(nums)):

if i!=j:

product *= nums[j]

answer.append(product)

return answer

これはLeetCodeでは時間オーバーになります。

解答2:最初に全要素の掛算を行い、後から要素ごとに割り算

class Solution:
    def productExceptSelf(self, nums: List[int]) -> List[int]:
        #Initilize variables
        products_of_all = 1
        #This variable has the result of all elements without zero.
        #And this is used as element of answer when nums has within one zero and
        #iterate is zero in bellow for in loop.
        products_of_all_exclude_zero = 1
        count_zero = 0
        #Start a for loop iterate nums.
        for i in nums:
            #i-th element is producted to "products_of_all".
            products_of_all *= i
            #If i is not zero,
            if i!=0:
                #
                products_of_all_exclude_zero *= i
                print(products_of_all_exclude_zero)
            #If i is zero,
            if i==0:
                #count_zero is incremented.
                count_zero += 1
        #The array has all zero elements if nums has more than 2 zeros.
        if count_zero >= 2:
            return [0]*len(nums)
        #
        else:
            answer = []
            #Start a for loop when "nums" has zero within 1.
            for i in nums:
                if i!=0:
                    answer.append(products_of_all//i)
                    print(products_of_all_exclude_zero,"i=0")
                else:
                    answer.append(products_of_all_exclude_zero)
                    print(products_of_all_exclude_zero,"i=1")
            
            return answer

class Solution:

def productExceptSelf(self, nums: List[int]) -> List[int]:

#Initilize variables

products_of_all = 1

#This variable has the result of all elements without zero.

#And this is used as element of answer when nums has within one zero and

#iterate is zero in bellow for in loop.

products_of_all_exclude_zero = 1

count_zero = 0

#Start a for loop iterate nums.

for i in nums:

#i-th element is producted to "products_of_all".

products_of_all *= i

#If i is not zero,

if i!=0:

products_of_all_exclude_zero *= i

print(products_of_all_exclude_zero)

#If i is zero,

if i==0:

#count_zero is incremented.

count_zero += 1

#The array has all zero elements if nums has more than 2 zeros.

if count_zero >= 2:

return [0]*len(nums)

else:

answer = []

#Start a for loop when "nums" has zero within 1.

for i in nums:

if i!=0:

answer.append(products_of_all//i)

print(products_of_all_exclude_zero,"i=0")

else:

answer.append(products_of_all_exclude_zero)

print(products_of_all_exclude_zero,"i=1")

return answer

解答3: Python, 英語コメント

"""
Question
 Let me check about my understand.
 I am given the variable "nums". It is array with only integer nums.
 I have to return array.
 The array's each element has the result of the product of all element except for itself.
 For example, i-th element of returned array has the product of all element except for i-th element.

Assumption
 Can I assume some following?
 (Can I make some following assumption?)
 (I wanna make some assumption.)
 
 -the length of nums is less than 10^4(ten to the power of 4)
 -nums may possibly have one or two zero.
 -each element of nums is positive number.
 -input array(nums) has at least two element

 Let me add assumptions if I come up with another.

Test cases
 -general cases
  [1,2,3,4] >>> [24,12,8,6]
  [1,2,0,3] >>> [0,0,6,0]
  [1,0,2,0] >>> [0,0,0,0]

 -edge cases
  [0,0,0] >>> [0,0,0]
  [] >>> out of consideradtion

Approach
 -Brute Forch
  Perfome for loop at least one time.
  in First loop I have some infromations
   where is zero.
   How many zeros does nums have.
   Store the result of the produt of each element.
  And Perfome next process.
  If nums has no zero.
  I am going to return the array.
  The array's each element is the result of divide with product of all element by each element.

  or if nums has two or more zero.
  Return the array with all element are zero.

  or if nums has only one zero.
  Return the array...
  
  time O(n)
  space O(n)
"""            



class Solution:
    def productExceptSelf(self, nums: List[int]) -> List[int]:
        

        zero_count = 0
        product_all = 1
        product_with_one_zero = 1
        zero_index = 0
        for i in range(len(nums)):
            product_all *= nums[i]
            if nums[i] == 0:
                zero_count += 1
                zero_index = i
        
        if zero_count == 1:
            for i in range(len(nums)):
                if i != zero_index:
                    product_with_one_zero *= nums[i]
            answer = [0]*len(nums)
            answer[zero_index] = product_with_one_zero
            return answer
        
        elif zero_count > 1:
            return [0]*len(nums)
            
        else:
            answer = []
            for i in nums:
                answer.append(product_all//i)
            return answer

"""

Question

Let me check about my understand.

I am given the variable "nums". It is array with only integer nums.

I have to return array.

The array's each element has the result of the product of all element except for itself.

For example, i-th element of returned array has the product of all element except for i-th element.

Assumption

Can I assume some following?

(Can I make some following assumption?)

(I wanna make some assumption.)

-the length of nums is less than 10^4(ten to the power of 4)

-nums may possibly have one or two zero.

-each element of nums is positive number.

-input array(nums) has at least two element

Let me add assumptions if I come up with another.

Test cases

-general cases

[1,2,3,4] >>> [24,12,8,6]

[1,2,0,3] >>> [0,0,6,0]

[1,0,2,0] >>> [0,0,0,0]

-edge cases

[0,0,0] >>> [0,0,0]

[] >>> out of consideradtion

Approach

-Brute Forch

Perfome for loop at least one time.

in First loop I have some infromations

where is zero.

How many zeros does nums have.

Store the result of the produt of each element.

And Perfome next process.

If nums has no zero.

I am going to return the array.

The array's each element is the result of divide with product of all element by each element.

or if nums has two or more zero.

Return the array with all element are zero.

or if nums has only one zero.

Return the array...

time O(n)

space O(n)

"""

class Solution:

def productExceptSelf(self, nums: List[int]) -> List[int]:

zero_count = 0

product_all = 1

product_with_one_zero = 1

zero_index = 0

for i in range(len(nums)):

product_all *= nums[i]

if nums[i] == 0:

zero_count += 1

zero_index = i

if zero_count == 1:

for i in range(len(nums)):

if i != zero_index:

product_with_one_zero *= nums[i]

answer = [0]*len(nums)

answer[zero_index] = product_with_one_zero

return answer

elif zero_count > 1:

return [0]*len(nums)

else:

answer = []

for i in nums:

answer.append(product_all//i)

return answer

解答の考え方は解答2と同じ。

実際の英語の面接をイメージして、議論すべきことを最初に書いてみた

終わりに

補足・参考・感想

問題を分類しました。テーマごとに集中して問題を解くことができます。

LeeetCodeの問題をアルゴリズムとデータ構造による分類

LeetCodeに特有の内容など、知っておくと役に立つかもしれないことをまとめました。

解答前に知っておくと役に立つかもしれない情報

他の問題もどうぞ

前：

次：

LeetCode 解答・解説記事一覧