Pythonで2つの配列の共通部分（交差）を効率的に求める方法

問題概要

2つの配列 A と B が与えられたとき、これらの配列に共通して含まれる要素（交差・共通部分）を求めます。例えば、A = [1, 4, 5, 3, 6]、B = [2, 3, 5, 7, 9] の場合、両方の配列に存在する要素は 3 と 5 だけなので、結果は [3, 5] となります。

この種の問題では重複の扱いがポイントになります。ある要素が両方の配列に複数回現れる場合は、その出現回数のうち少ない方の回数だけ結果に含める必要があります。

解法のアプローチ

この問題は、ハッシュマップ（Pythonでは辞書型 dict）を使って要素の出現頻度を管理することで、効率的に解くことができます。手順は以下の通りです。

• 2つの配列 A と B を受け取る
• A の長さが B より小さい場合は、両者を入れ替える（より短い方の配列で頻度マップを作ることで、メモリ使用量を最小限に抑えられる）
• 配列内の各要素の出現頻度を計算し、辞書 m に格納する
• B の各要素 e に対して、e が m に存在し、かつその頻度が 0 より大きい場合は次の処理を行う
  • m[e] の値を 1 減らす
  • e を結果の配列に追加する
• 最終的に結果の配列を返す

頻度を減らしながら処理することで、片方の配列にある同じ要素が何度現れても、もう片方の配列での出現回数を超えてカウントされることはありません。

実装例

以下の実装を見ると、処理の流れがより理解しやすくなります。

class Solution(object):
    def intersect(self, nums1, nums2):
        """
        :type nums1: List[int]
        :type nums2: List[int]
        :rtype: List[int]
        """
        m = {}
        if len(nums1) < len(nums2):
            nums1, nums2 = nums2, nums1
        for i in nums1:
            if i not in m:
                m[i] = 1
            else:
                m[i] += 1
        result = []
        for i in nums2:
            if i in m and m[i]:
                m[i] -= 1
                result.append(i)
        return result

ob1 = Solution()
print(ob1.intersect([1,4,5,3,6], [2,3,5,7,9]))

入力

[1,4,5,3,6]
[2,3,5,7,9]

出力

[3,5]

計算量の評価

時間計算量は O(n + m)（n、m はそれぞれの配列の長さ）です。各配列を一度ずつ走査するだけで済むため、ネストしたループで総当たり的に比較する O(n × m) のアプローチよりも大幅に高速です。

空間計算量については、頻度マップを短い方の配列で作成しているため O(min(n, m)) となり、メモリの無駄を抑えた実装になっています。