Javaでソートされていない整数配列から欠落している正の数を見つける方法

はじめに

ソートされていない整数の配列が与えられていると仮定しましょう。この課題は、範囲 [0〜n] の中で、与えられた配列に存在しない正の欠損数を見つけることです。以下に具体例を示します。

入力例1

N = 9
arr = [0,2,5,9,1,7,4,3,6]

出力:

8

説明: このソートされていない配列において、「8」だけが欠落している正の整数であるため、出力は「8」になります。

入力例2

N = 1
arr = [0]

出力:

1

説明: この配列では、「1」だけが欠落している正の整数であるため、出力は「1」になります。

この問題へのアプローチ

この問題にはいくつかの解法がありますが、線形時間 O(n) かつ定数領域 O(1) で効率よく解くことができます。

配列のサイズは n であり、その要素はちょうど [0〜n] の範囲に収まっていることが分かっています。そこで、各要素とそのインデックス、さらに「n」を含めて XOR 演算を行うと、配列から欠落している一意の数を求めることができます。

これは XOR の性質によるものです。同じ値同士の XOR は 0 になり、すべての値を順に XOR していくと、ペアにならなかった値、すなわち欠損数だけが最後に残る仕組みです。

解法の手順

• [0〜n] の範囲の要素を含むサイズ N の配列を入力として受け取ります。
• 整数型関数 findMissingNumber(int arr[], int size) が、配列とそのサイズを引数として受け取り、欠損数を返します。
• 欠損数を格納する変数を初期化し(初期値は配列のサイズ n)、ここに対して XOR 演算を実行していきます。
• 配列の全要素を走査し、各要素とそのインデックスを欠損数候補に対して XOR 演算します。
• 最終的に残った値が欠損数となるため、それを返します。

実装例

public class Solution {
    public static int findMissingNumber(int arr[], int size){
        int missing_no= size;
        for(int i=0;i<size;i++){
            missing_no^= i^arr[i];
        }
        return missing_no;
    }
    public static void main(String[] args){
        int arr[] = {0,4,2,1,6,3};
        int n = arr.length;
        int a=findMissingNumber(arr, n);
        System.out.println(a);
    }
}

出力

上記のコードを実行すると、次の出力が得られます。

5

与えられた配列 {0,4,2,1,6,3} では「5」が欠落しているため、プログラムは 5 を返します。