C++でソートされていない配列からk番目に欠落している要素を見つける方法

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

具体的には、配列内の最小値から最大値までの範囲において存在しない数値を順に数え、そのうちk番目のものを特定します。それでは、問題を解くための手順を順番に見ていきましょう。

解決手順

• ソートされていない配列を初期化します。
• すべての要素をセット（unordered_set）に挿入し、高速な存在判定を可能にします。
• 配列から最大値と最小値を求めます。
• 最小値から最大値まで走査するループを作成し、カウント用の変数を管理します。
  • 現在の数値がセットに存在しない場合、カウントを1増やします。
  • カウントがkに達したら、その時点の数値を答えとして返します。

コード例

実際のコードを見てみましょう。

#include <bits/stdc++.h>
using namespace std;
int findMissingNumber(int arr[], int n, int k) {
    unordered_set<int> numbers;
    int count = 0;
    for (int i = 0; i < n; i++) {
        numbers.insert(arr[i]);
    }
    int max = *max_element(arr, arr + n);
    int min = *min_element(arr, arr + n);
    for (int i = min + 1; i < max; i++) {
        if (numbers.find(i) == numbers.end()) {
            count++;
        }
        if (count == k) {
            return i;
        }
    }
    return -1;
}
int main() {
    int arr[] = { 1, 10, 3, 2, 5 }, n = 5;
    int k = 3;
    cout << findMissingNumber(arr, n, k) << endl;
    return 0;
}

出力結果

上記のコードを実行すると、次のような結果が得られます。

7

処理の流れの解説

この例では、配列 {1, 10, 3, 2, 5} の最小値は 1、最大値は 10 です。この範囲で欠けている数値は「4, 6, 7, 8, 9」の5つです。k = 3 なので、3番目に欠けている数値である 7 が出力されます。

なお、unordered_set を使うことで各要素の存在確認が O(1) で行えるため、全体の計算量は O(n + m) になります（n は配列のサイズ、m は最小値と最大値の差）。もし k 番目の欠落要素が見つからない場合は、-1 が返される仕組みです。

まとめ

本チュートリアルでは、C++の unordered_set を活用して、ソートされていない配列から k 番目に欠落している要素を効率的に見つける方法を学びました。この手法は、データの前処理にハッシュセットを用いることで、繰り返しの探索コストを大幅に削減できる好例です。チュートリアルの内容についてご質問がある場合は、コメント欄でお気軽にお知らせください。