2つの配列の共通要素を見つける方法


  1. ブルートフォース法: 2つの配列を順番に比較し、共通要素を見つける方法です。各要素を1回ずつ全ての要素と比較するので、計算量はO(n*m)となります(nとmは2つの配列の要素数)。

    def find_intersection(arr1, arr2):
       intersection = []
       for num1 in arr1:
           for num2 in arr2:
               if num1 == num2:
                   intersection.append(num1)
       return intersection
  2. ハッシュセットを使用する方法: 1つの配列をハッシュセットに変換し、もう一方の配列の要素がハッシュセットに含まれているかを調べます。要素の検索にはハッシュセットの特性を利用するため、計算量はO(n+m)となります。

    def find_intersection(arr1, arr2):
       set1 = set(arr1)
       intersection = []
       for num in arr2:
           if num in set1:
               intersection.append(num)
       return intersection
  3. ソートしてマージする方法: 2つの配列をソートし、マージしながら共通要素を見つけます。ソートには一般的にO(n log n)の時間がかかりますが、マージにはO(n+m)の時間がかかりますので、計算量はO(n log n)となります。

    def find_intersection(arr1, arr2):
       arr1.sort()
       arr2.sort()
       intersection = []
       i = j = 0
       while i < len(arr1) and j < len(arr2):
           if arr1[i] == arr2[j]:
               intersection.append(arr1[i])
               i += 1
               j += 1
           elif arr1[i] < arr2[j]:
               i += 1
           else:
               j += 1
       return intersection

これらは一部のアプローチ例ですが、他にも様々な方法があります。選択する方法は、データの特性や要件によって異なります。