C#で3つのソート済み配列から共通要素を見つけるプログラム

はじめに

C#では、すでに昇順にソートされた3つの配列に含まれる共通要素を、効率的に求めることができます。各配列にインデックス（ポインタ）を1つずつ用意し、それらを同時に進めていく手法を使うことで、計算量 O(n1 + n2 + n3) の線形時間で処理できます。ここでは、その実装方法をわかりやすく解説します。

アルゴリズムの流れ

まず、比較対象となる3つのソート済み配列を初期化します。

int []one = {20, 35, 57, 70};
int []two = {9, 35, 57, 70, 92};
int []three = {25, 35, 55, 57, 67, 70};

次に、whileループを使って3つの配列を同時に走査します。3つの配列の現在位置にある値がすべて一致していれば、それを共通要素として出力し、3つのインデックスをそれぞれ進めます。一致していない場合は、最も小さい値を持つ側のインデックスだけを進めることで、効率よく比較を続けます。

while (i < one.Length && j < two.Length && k < three.Length) {
   if (one[i] == two[j] && two[j] == three[k]) {
      Console.Write(one[i] + " ");
      i++;j++;k++;
   }
   else if (one[i] < two[j])
      i++;
   else if (two[j] < three[k])
      j++;
   else
      k++;
}

サンプルコード

以下のコードを実行すると、3つのソート済み配列から共通要素を抽出できます。

using System;
class Demo {
   static void commonElements(int []one, int []two, int []three) {
      int i = 0, j = 0, k = 0;
      while (i < one.Length && j < two.Length && k < three.Length) {
         if (one[i] == two[j] && two[j] == three[k]) {
            Console.Write(one[i] + " ");
            i++;j++;k++;
         }
         else if (one[i] < two[j])
            i++;
         else if (two[j] < three[k])
            j++;
         else
            k++;
      }
   }
   public static void Main() {
      int []one = {20, 35, 57, 70};
      int []two = {9, 35, 57, 70, 92};
      int []three = {25, 35, 55, 57, 67, 70};

      Console.Write("Common elements: ");

      commonElements(one, two, three);
   }
}

実行結果

Common elements: 35 57 70 

ポイント解説

• このアルゴリズムは、配列があらかじめソートされていることが前提となります。
• 各配列を一度だけ走査するため、計算量は O(n1 + n2 + n3) と非常に効率的です。
• いずれか1つの配列の末尾に達した時点でループが終了するため、無駄な比較が発生しません。