てくてくテック

【LeetCode】349. Intersection of Two Arrays 17日目

leetcode

どーも!

今日もやっていきます!

349. Intersection of Two Arrays

今回の問題は以下です。

問題の解説をしておくと、二つの配列中から同一の要素を抽出しろ...的な感じです...!

例をお借りすると....

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

Input: nums1 = [4,9,5], nums2 = [9,4,9,8,4]
Output: [9,4]

上記のように、num1, num2二つのリストで虚通して含まれている要素のみ抽出したリストを書き出します。

出力の順番は自由でいいらしいです。

では、アルゴリズムを考えていきます。

アルゴリズム

最初考えたのは長さの短いリストの値を一個づつ見ていき、その値がもう一方に含まれていたら空のresultリストへ追加していく...と言うものです。

ただし、追加する際、その値がresultリストに含まれていないことも条件に含めます。

イメージは以下のような感じです。

わかりづらいですが、最初に小さいリストがnums1にくるようにしています。

そして、そのあと、for文で短いリストを回し、その値をoutputへ追加していきます。

その際、num2と重複しているか、そしてoutputにまだ存在していないか?を確認します。

これで、いったんはできそうです。

ただ、おそらくPythonのことなので、もっと短くかけるだろうな...と。

結局以下のように、二つの配列の重複部分を取得できればいいはず...なので...

まず重複は必要ないため、set関数で重複を排除します。

その排除した配列で一致する部分を掛け算で出せば...(AND条件の積集合ですね)それが答えのはずです。

(以下図で一箇所だけ...正確にはset関数を通すと... [1,2,2,1] ,[2,2]ではなく、[1,2], [2]ですね...w)

上記をそのままプログラムとして書いてみると...?

きっと解けそうな気がします...!

最初にsetで二つの配列それぞれ、自身の重複をあらかじめ排除しておきます。

その結果、返り値が集合型になるため、list()でキャストしてあげます。(回答はリスト型で返す必要があるため)

そしてキャストしたあと、最後に二つの配列を"&"で積集合を返します。(最初*で掛け算したらいけるんじゃね?とおもったらpythonでは&でした...)

これで問題なく動作しました!

では、最後に提出したコードを置いておきます。

提出したコード

class Solution:
    def intersection(self, nums1: List[int], nums2: List[int]) -> List[int]:
        return list(set(nums1) & set(nums2))


# 以下、提出結果
Runtime: 40 ms, faster than 93.20% of Python3 online submissions for Intersection of Two Arrays.
Memory Usage: 14.4 MB, less than 76.55% of Python3 online submissions for Intersection of Two Arrays.

Pythonは短くかける...と言うのが最近理解できてきた気がします...!

モバイルバージョンを終了