C#で組み込み関数を使わずにソート済み配列から欠落した数値を見つける3つの方法

C#では、組み込み関数に頼らなくても、いくつかのアルゴリズム的なアプローチによってソート済み配列の中から欠落している数値を効率的に特定できます。本記事では、代表的な3つの方法を具体的なコード例とともに解説します。

方法1：等差数列の和の公式を利用する

0からnまでの連続する整数の合計は、有名な公式「n(n+1)/2」で求めることができます。まず配列の要素数からこの公式で理論上の合計値を算出し、次に実際に配列内の全要素を足し合わせた値を求めます。この2つの差分こそが、欠落している数値です。

• 計算量：O(n)
• 追加メモリ：不要（O(1)）

方法2：ブール型の補助配列を使用する

元の配列の要素数 + 1 のサイズを持つbool型の新しい配列を作成します。元の配列全体を走査しながら、出現した数値に対応するインデックスの値をtrueに設定していきます。最後までfalseのまま残っているインデックスが、欠落している数値を示しています。

• 計算量：O(n)
• 追加メモリ：補助配列分が必要（O(n)）

方法3：XOR（排他的論理和）演算を利用する

XOR演算には「同じ値同士を演算すると0になる」「0との演算では値が変わらない」という性質があります。この性質を利用して配列全体を順にXORで処理すると、ペアにならない数値、すなわち欠落している数値だけが最終的に残ります。

• 計算量：O(n)
• 追加メモリ：不要（O(1)）

サンプルコード

using System;
namespace ConsoleApplication{
    public class Arrays{
        public int MissingNumber1(int[] arr){
            int totalcount = 0;
            for (int i = 0; i < arr.Length; i++){
                totalcount += arr[i];
            }
            int count = (arr.Length * (arr.Length + 1)) / 2;
            return count - totalcount;
        }
        public int MissingNumber2(int[] arr){
            bool[] tempArray = new bool[arr.Length + 1];
            int element = -1;
            for (int i = 0; i < arr.Length; i++){
                int index = arr[i];
                tempArray[index] = true;
            }
            for (int i = 0; i < tempArray.Length; i++){
                if (tempArray[i] == false){
                    element = i;
                    break;
                }
            }
            return element;
        }
        public int MissingNumber3(int[] arr){
            int result = 1;
            for (int i = 0; i < arr.Length; i++){
                result = result ^ arr[i];
            }
            return result;
        }
    }
    class Program{
        static void Main(string[] args){
            Arrays a = new Arrays();
            int[] arr = { 0, 1, 3, 4, 5 };
            Console.WriteLine(a.MissingNumber1(arr));
            Console.WriteLine(a.MissingNumber2(arr));
            Console.WriteLine(a.MissingNumber3(arr));
            Console.ReadLine();
        }
    }
}

実行結果

2
2
2

この例では、配列 { 0, 1, 3, 4, 5 } から数値「2」が欠落しているため、3つのメソッドすべてが正しく「2」を出力します。

まとめ

メモリ効率を重視するなら和の公式またはXOR演算、実装のわかりやすさやデバッグのしやすさを重視するならブール配列方式がおすすめです。配列のサイズや要件に応じて、最適な手法を選択しましょう。