C++で1〜Nの範囲の配列から欠落している4つの数値を検出する方法

概要

与えられた配列には重複のない整数が格納されており、各要素は 1 以上 N 以下の範囲に収まっています。配列のサイズは N−4 であるため、1 から N までの数値のうちちょうど 4 つが欠落していることになります。本記事では、その欠落している 4 つの数値を昇順で求めるアルゴリズムを解説します。

入力例と出力例

例 1

arr[] = {3, 6, 7, 4, 10}

出力: 1 2 5 8 9

例 2

arr[] = { 2, 8, 4, 13, 6, 11, 9, 5, 10 }

出力: 1 3 7 12

解法の考え方

基本のアプローチ：O(N) の補助配列を使う方法

最もシンプルな解法は、サイズ N の補助配列を用意して出現済みの要素にフラグを立てる方法です。入力配列を走査しながら該当する位置にマークを付け、最後にマークされていないインデックスを出力します。ただし、この方法では O(N) の追加メモリが必要になります。

改善版：O(1) の補助空間で解く方法

ここで問題になるのが、「補助空間を O(1) に抑えるにはどうすればよいか」という点です。鍵となるのは、元の配列自身の符号（正負）をマーク代わりに使うことです。手順は以下のとおりです。

1. まず、欠落しうる 4 つの数値を記録するために長さ 4 のヘルパー配列 helper を用意し、すべて 0 で初期化します。
2. 次に、i = 0 から配列の長さ未満までループを回し、i 番目の要素の絶対値を変数 temp に格納します。
3. temp の値に応じて、次のように処理を振り分けます。

• temp が入力配列の長さ以下の場合： 出現済みの印として、arr[temp − 1] の要素に −1 を掛けます。
• temp が入力配列の長さより大きい場合： 出現済みの印として、helper[temp % 配列長] の位置に −1 を設定します。

マーク付けが完了したら、まず入力配列を走査します。値がまだ正のまま残っているインデックス i は「数値 i + 1 が入力配列に出現しなかった」ことを意味するため、i + 1 を出力します。

続いて helper 配列を走査します。値がまだ正（または 0）のまま残っているインデックス i は「数値 配列長 + i + 1 が出現しなかった」ことを意味するため、配列長 + i + 1 を出力します。

C++ 実装例

// サイズNの配列から、1〜N+4の範囲の中で
// 欠落している4つの要素を検索するC++プログラム
#include <bits/stdc++.h>
using namespace std;

// O(N)時間・O(1)補助空間で欠落している4つの数値を検索する
void missing4(int arr1[], int n1){
    // 入力配列の長さより大きい4つの候補を追跡するための配列
    // ※Javaの場合、helperは自動的に0で初期化される
    int helper[4];
    // 入力配列を走査し、訪問済みの要素に
    // arr[]またはhelper[]内で負の値としてマークを付ける
    for (int i = 0; i < n1; i++) {
        int temp1 = abs(arr1[i]);
        // 絶対値が配列の長さ以下なら、arr1[]内に存在をマーク
        if (temp1 <= n1)
            arr1[temp1 - 1] *= (-1);
        // 長さより大きい場合はhelper[]内に存在をマーク
        else if (temp1 > n1) {
            if (temp1 % n1 != 0)
                helper[temp1 % n1 - 1] = -1;
            else
                helper[(temp1 % n1) + n1 - 1] = -1;
        }
    }
    // マークされていない要素をすべて出力する
    for (int i = 0; i < n1; i++)
        if (arr1[i] > 0)
            cout << (i + 1) << " ";
    for (int i = 0; i < 4; i++)
        if (helper[i] >= 0)
            cout << (n1 + i + 1) << " ";
    return;
}

// ドライバーコード
int main(){
    int arr1[] = { 2, 8, 4, 13, 6, 11, 9, 5, 10 };
    int n1 = sizeof(arr1) / sizeof(arr1[0]);
    missing4(arr1, n1);
    return 0;
}

注意： C++ ではローカル配列は自動的にゼロ初期化されません。実際に動作させる際は、int helper[4] = {}; のように明示的に初期化することをおすすめします（Java の場合は自動的に 0 で初期化されます）。

出力

1 3 7 12

計算量

• 時間計算量： O(N) — 入力配列を数回走査するだけです。
• 補助空間： O(1) — 長さ 4 の固定サイズの配列のみを使用します。