【LeetCode】 350. Intersection of Two Arrays II 解答・解説【Python】

はじめに
詳細
1. 問題
  1. 原文
  2. 内容(和訳)
2. 解答
  1. 解答1：Python, brute force
終わりに

はじめに

ポイント

総当たり法で解答

この記事のメリット

配列操作の初歩が学べる

この記事が役立ちそうな方

配列の扱いに慣れたい方
総当たり法(brute force)から時間計算量を改善するコードを書きたい方

詳細

問題

原文

Given two integer arrays nums1 and nums2, return an array of their intersection. Each element in the result must appear as many times as it shows in both arrays and you may return the result in any order.

Example 1:

Input: nums1 = [1,2,2,1], nums2 = [2,2] Output: [2,2]

1
2

Input: nums1 = [1,2,2,1], nums2 = [2,2]
Output: [2,2]

Example 2:

Input: nums1 = [4,9,5], nums2 = [9,4,9,8,4] Output: [4,9] Explanation: [9,4] is also accepted.

1
2
3

Input: nums1 = [4,9,5], nums2 = [9,4,9,8,4]
Output: [4,9]
Explanation: [9,4] is also accepted.

Constraints:

1 <= nums1.length, nums2.length <= 1000

0 <= nums1[i], nums2[i] <= 1000

Follow up:

What if the given array is already sorted? How would you optimize your algorithm?

What if nums1‘s size is small compared to nums2‘s size? Which algorithm is better?

What if elements of nums2 are stored on disk, and the memory is limited such that you cannot load all elements into the memory at once?

内容(和訳)

2つの配列nums1,nums2が与えられます。

両方の配列に出現する要素を集めた配列を返してください。

戻り値の配列の各要素は、それぞれの配列で出現した回数のみである必要があります。

戻り値の配列の各要素は任意の順番で良いです。

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

解答

解答1：Python, brute force

class Solution:
    def intersect(self, nums1: List[int], nums2: List[int]) -> List[int]:
        #戻り値となるリストを用意
        answer = []

        #nums1の各要素を一巡するまで繰り返す
        for i in nums1:
            #i(nums1の各要素)がnums2にある場合
            if i in nums2:
                #nums2からiを取り除く
                nums2.remove(i)
                #answerにiを追加
                answer.append(i)
        
        #answerを返す
        return answer

class Solution:

def intersect(self, nums1: List[int], nums2: List[int]) -> List[int]:

#戻り値となるリストを用意

answer = []

#nums1の各要素を一巡するまで繰り返す

for i in nums1:

#i(nums1の各要素)がnums2にある場合

if i in nums2:

#nums2からiを取り除く

nums2.remove(i)

#answerにiを追加

answer.append(i)

#answerを返す

return answer

・時間計算量：O(n^2)

・空間計算量：O(n)

問題文の制約より、配列の要素数がそれぞれ1000以内なのでこの方法でも間に合いました。

1 <= nums1.length, nums2.length <= 1000

終わりに

補足・参考・感想

疑問が解決した方はこちらへ

前：404. Sum of Left Leaves

次：121. Best Time to Buy and Sell Stock

LeetCode 解答・解説記事一覧

疑問が解決しない方はこちらへ

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

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