C++で指定されたn個の範囲からk番目に小さい要素を検索する方法

問題の概要

この問題では、n個の数値範囲と整数kが与えられます。これらの範囲に含まれるすべての整数を結合してできる配列の中から、k番目に小さい要素を見つけることが課題です。

具体的には、各範囲内のすべての整数を集めて昇順に並べた配列を作成し、その中のk番目の値を求めることになります。

問題例

入力：ranges = {{2, 5}, {7, 9}, {12, 15}}, k = 9

出力：13

説明：

作成される配列は {2, 3, 4, 5, 7, 8, 9, 12, 13, 14, 15} となります。この配列を小さい順に数えると、9番目に小さい要素は13です。

解決アプローチ

最もシンプルな解法は、すべての範囲から配列を作成する方法です。各範囲は連続した整数で構成されており、開始値から終了値へ順に格納していくため、作成される配列は自動的に昇順にソートされます。したがって、配列のk番目の値（インデックスでは k−1 番目）を取得するだけで答えが得られます。

アルゴリズムの手順

1. すべての範囲を走査し、各範囲の開始値から終了値までの整数を順番に配列へ格納します。
2. 配列のサイズがk以上であるかどうかを確認します（kが範囲外の場合はエラー扱いにします）。
3. k番目に小さい要素 rangeArr[k−1] を出力します。

C++プログラムの実装例

#include <iostream>
using namespace std;

int main() {
    int arr[][2] = {{2, 5}, {7, 9}, {12, 15}};
    int n = sizeof(arr) / sizeof(arr[0]);
    int k = 9;

    // 範囲内の全要素を格納する配列
    int rangeArr[1000];
    int size = 0;

    for (int i = 0; i < n; i++)
        for (int j = arr[i][0]; j <= arr[i][1]; j++) {
            rangeArr[size] = j;
            size++;
        }

    if (k >= 1 && k <= size)
        cout << k << "番目に小さい要素は " << rangeArr[k - 1] << endl;
    else
        cout << "無効なインデックスです" << endl;

    return 0;
}

出力

9番目に小さい要素は 13

計算量の評価

• 時間計算量：O(N × L)。Nは範囲の個数、Lは各範囲に含まれる要素数です。
• 空間計算量：結合後の配列サイズ分のメモリが必要になります。

より効率的なアプローチ：二分探索

範囲が非常に大きい場合、実際に配列を作成するとメモリや処理時間が不足する可能性があります。そこで役立つのが二分探索です。「x以下の要素がk個以上存在する最小のx」を探すことで、配列を作成せずに答えを求められます。

ある値x以下の要素数は、各範囲 [l, r] に対して「x ≥ l ならば min(x, r) − l + 1 を加算」するだけでO(N)で計算できます。全体の計算量はO(N log(最大値))となり、巨大な範囲でも高速に動作します。

#include <iostream>
#include <vector>
#include <climits>
#include <algorithm>
using namespace std;

// x以下の要素数を数える
long long countUpTo(long long x, const vector<pair<int,int>>& ranges) {
    long long cnt = 0;
    for (auto& [l, r] : ranges) {
        if (x >= l) cnt += min(x, (long long)r) - l + 1;
    }
    return cnt;
}

int main() {
    vector<pair<int,int>> ranges = {{2, 5}, {7, 9}, {12, 15}};
    int k = 9;

    long long lo = 0, hi = INT_MAX;
    while (lo < hi) {
        long long mid = lo + (hi - lo) / 2;
        if (countUpTo(mid, ranges) >= k) hi = mid;
        else lo = mid + 1;
    }

    cout << k << "番目に小さい要素は " << lo << endl;
    return 0;
}

出力

9番目に小さい要素は 13

まとめ

範囲から配列を作成するシンプルな方法は直感的で理解しやすく、小規模な入力には十分です。一方、範囲が大きい・広い場合は、配列を実体化せずに済む二分探索ベースの手法が有効です。入力の制約に応じて適切なアルゴリズムを選択することが重要です。