3つのソート済み配列から共通要素を見つけるPythonプログラムの書き方

この記事では、Pythonを使って3つのソート済み配列（リスト）に共通して含まれる要素を効率的に見つける方法を解説します。

基本的な流れは以下のとおりです。まず、ユーザーが入力した3つの未ソートのリストを用意し、それぞれをsorted()関数で昇順に並べ替えます。その後、各リストの先頭から同時に走査を行い、3つのリストの現在位置にある要素がすべて一致するかどうかを確認します。一致していればその要素を出力し、一致していなければ最も小さい値を持つインデックスを進めて次の要素へ移動します。

処理の概要

配列のサイズをそれぞれ n1、n2、n3 とし、各配列の走査位置を示すインデックスを i = 0、j = 0、k = 0 で初期化します。3つのインデックスがそれぞれ配列の範囲内である間ループを続け、要素を比較しながら共通要素を抽出します。

実行例

A = {1, 2, 3, 4, 5}
B = {2, 5, 12, 22, 7}
C = {1, 9, 2, 89, 80}

出力結果

2

アルゴリズム

commonele(A1, A2, A3, n1, n2, n3)
/* A1, A2, A3 はソート済みの整数配列、
   size1, size2, size3 はそれぞれの配列のサイズ */

ステップ1: 各配列の開始インデックスを初期化する
   i = 0, j = 0, k = 0

ステップ2: いずれかの配列が空になるまで3つの配列を反復処理する
   while (i < size1 && j < size2 && k < size3)

ステップ3: A1[i]、A2[j]、A3[k] の値を比較する。
   3つとも同じ値なら出力し、全インデックスを進める。
   異なる場合は最小の値を持つインデックスだけを進める。

ステップ4: ループ終了

サンプルコード

# 3つのソート済み配列の共通要素を出力するプログラム
def commonele(X, Y, Z, n1, n2, n3):
    i, j, k = 0, 0, 0
    print("共通要素は次のとおりです ::>")
    while (i < n1 and j < n2 and k < n3):
        if (X[i] == Y[j] and Y[j] == Z[k]):
            print(X[i])
            i += 1
            j += 1
            k += 1
        elif X[i] < Y[j]:
            i += 1
        elif Y[j] < Z[k]:
            j += 1
        else:
            k += 1

# ドライバープログラム
A = list()
B = list()
C = list()
n1 = int(input("1つ目のリストのサイズを入力してください ::"))
n2 = int(input("2つ目のリストのサイズを入力してください ::"))
n3 = int(input("3つ目のリストのサイズを入力してください ::"))
print("1つ目のリストの要素を入力してください ::")
for i in range(int(n1)):
    k = int(input(""))
    A.append(k)
print("2つ目のリストの要素を入力してください ::")
for j in range(int(n2)):
    k1 = int(input(""))
    B.append(k1)
print("3つ目のリストの要素を入力してください ::")
for j in range(int(n3)):
    k1 = int(input(""))
    C.append(k1)
X = sorted(A)
Y = sorted(B)
Z = sorted(C)
print("ソート後の1つ目のリスト ::>", X)
print("ソート後の2つ目のリスト ::>", Y)
print("ソート後の3つ目のリスト ::>", Z)
commonele(X, Y, Z, n1, n2, n3)

実行結果

Enter the size of the First List :: 4
Enter the size of the Second List :: 4
Enter the size of the Third List :: 5
Enter the Element of First List ::
23
12
45
8
Enter the Element of Second List ::
34
8
45
120
Enter the Element of Third List ::
2
4
8
45
1
First Sorted List ::> [8, 12, 23, 45]
Second Sorted List ::> [8, 34, 45, 120]
Third Sorted List ::> [1, 2, 4, 8, 45]
Common elements are ::>
8
45

アルゴリズムのポイント

この手法の優れた点は、3つのポインタ（インデックス）を1回の走査だけで進めることです。具体的には次のように動作します。

• 3つの値が完全に一致した場合：その値は共通要素なので出力し、3つのインデックスをすべて1つ進めます。
• X[i] が Y[j] より小さい場合：X[i] は他方のリストに存在しないため、i を進めます。
• Y[j] が Z[k] より小さい場合：同様に j を進めます。
• それ以外の場合：k を進めます。

この方法により、計算量は O(n1 + n2 + n3) となり、3重ループで総当たり的に比較する O(n1 × n2 × n3) の素朴なアプローチと比べて大幅に高速です。すでにソート済みのデータに対しては、この「3ポインタ方式」が最も効率的な解法の一つといえます。