C++でソート済み配列からk番目に欠落している要素を求める方法

このチュートリアルでは、与えられたソート済み配列の中からk番目に欠落している要素を効率的に見つけるプログラムをC++で作成します。

例えば、配列 {1, 2, 3, 5, 10} の場合、最小値1から最大値10までの間に存在しない数値は「4, 6, 7, 8, 9」です。この中で3番目に欠けている数は「7」となります。それでは、問題を解くための手順を見ていきましょう。

アルゴリズムの手順

• ソート済み配列を初期化します。
• 変数 difference と count を宣言し、count を k で初期化します(まだ見つかっていない欠落要素の残り個数を管理します)。
• 配列を先頭から順に走査します。
  • 現在の要素と次の要素が連続していない場合(隣接する要素の差が1より大きい場合)：
    • 2つの要素の間にいくつの数が欠けているか(差分)を計算します。
    • 差分が count 以上であれば、答えは「現在の要素 + count」になるので、その値を返します。
    • そうでなければ、count から差分を引き、次の区間へ進みます。
• 配列全体を走査してもk番目の欠落要素が見つからない場合は -1 を返します。

C++での実装例

それでは、実際のコードを見てみましょう。

#include <bits/stdc++.h>
using namespace std;

int findMissingNumber(int arr[], int k, int n) {
    int difference, count = k;
    for (int i = 0; i < n - 1; i++) {
        if ((arr[i] + 1) != arr[i + 1]) {
            difference = arr[i + 1] - arr[i] - 1;
            if (difference >= count) {
                return arr[i] + count;
            } else {
                count -= difference;
            }
        }
    }
    return -1;
}

int main() {
    int arr[] = { 1, 2, 3, 5, 10 }, n = 5;
    int k = 3;
    cout << findMissingNumber(arr, k, n) << endl;
    return 0;
}

出力結果

上記のコードを実行すると、以下の結果が出力されます。

7

コードの解説

配列 {1, 2, 3, 5, 10}、k = 3 の場合の処理の流れは以下の通りです。

• 3と5の間には「4」の1つだけ欠落があるため、count は 3 - 1 = 2 になります。
• 5と10の間には「6, 7, 8, 9」の4つが欠落しています。差分4は count の2以上なので、「5 + 2 = 7」が答えとして返されます。

計算量

このアルゴリズムは配列を一度だけ走査するため、時間計算量は O(n)、追加のメモリ使用量は O(1) で非常に効率的です。なお、各位置における欠落数の性質を利用して二分探索を組み合わせれば、O(log n) への高速化も可能です。

まとめ

本チュートリアルでは、ソート済み配列からk番目に欠落している要素を線形時間で求める方法を学びました。チュートリアルの内容について質問がある場合は、コメント欄でお気軽にお知らせください。