C#で組み込み関数を使わずに配列内の欠損している数と重複している数を見つける方法

欠損している数を見つける方法

まず、元の配列よりも1つ大きいサイズのbool型配列を新しく作成します。次に、元の配列全体を走査し、各数値が出現したら新しく作成した配列の対応するインデックスを true に設定していきます。すべての走査が完了した後、この配列を先頭から再度走査し、最初に false となっているインデックスが欠損している数となります。

重複している数を見つける方法

同様に、int型のカウント用配列を別途用意します。各数値の出現状況を記録し、同じ数が2回目に出現した時点でその位置の値を2に更新します。走査後、最初に値が2になっているインデックスが、重複している数を示します。

サンプルコード

using System;
namespace ConsoleApplication{
    public class Arrays{
        public void MissingNumberAndRepeatedNumber(int[] arr){
            bool[] tempArray = new bool[arr.Length + 1];
            int missingelement = -1;
            int repeatingelement = -1;

            // 各数値の出現をマークする
            for (int i = 0; i < arr.Length; i++){
                int index = arr[i];
                if (!tempArray[index]){
                    tempArray[index] = true;
                }
            }

            // 最初のfalseが欠損している数
            for (int i = 0; i < tempArray.Length; i++){
                if (!tempArray[i]){
                    missingelement = i;
                    break;
                }
            }

            // 出現回数をカウントする
            int[] tempArray1 = new int[arr.Length + 1];
            for (int i = 0; i < arr.Length; i++){
                int index = arr[i];
                if (tempArray1[index] == 0){
                    tempArray1[index] = 1;
                }else if (tempArray1[index] == 1){
                    tempArray1[index] = 2;
                }
            }

            // 最初の2が重複している数
            for (int i = 0; i < tempArray1.Length; i++){
                if (tempArray1[i] == 2){
                    repeatingelement = i;
                    break;
                }
            }

            Console.WriteLine(missingelement);
            Console.WriteLine(repeatingelement);
        }
    }

    class Program{
        static void Main(string[] args){
            Arrays a = new Arrays();
            int[] arr = { 0, 1, 1, 3, 4 };
            a.MissingNumberAndRepeatedNumber(arr);
            Console.ReadLine();
        }
    }
}

実行結果

2
1

アルゴリズムのポイント

この手法はLINQなどの組み込み関数に一切依存せず、シンプルなループ処理だけで実装できます。時間計算量はO(n)、空間計算量はO(n)であり、非常に効率的です。ただし、配列の要素が0からnまでの範囲に収まっていることが前提となるため、インデックスとして直接アクセスできる点に注意してください。上記の例では、配列 { 0, 1, 1, 3, 4 } の中で「2」が欠損しており、「1」が重複していることが正しく検出されています。