C++のSTLを使って配列内のK番目に小さい・大きい要素を求める方法

はじめに

このチュートリアルでは、C++のSTL（標準テンプレートライブラリ）を使用して、ソートされていない配列からK番目に小さい要素を求めるプログラムを作成します。std::setを活用することで、手動でソートを行うことなく簡潔に実装できるのがポイントです。

解決手順

問題を解くための手順は以下の通りです。

• 配列と値kを初期化する。
• 空の順序付きセット（std::set）を初期化する。
• 配列を走査し、各要素をセットに挿入する。
• セットの先頭からk-1回だけイテレータを進める。
• その位置の値を返す。

std::setは要素を挿入した時点で自動的に昇順にソートされるため、先頭からk番目の要素にアクセスすれば、それが配列全体でk番目に小さい値になります。

コード例

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

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

int findKthSmallestNumber(int arr[], int n, int k) {
    set<int> s;
    for (int i = 0; i < n; i++) {
        s.insert(arr[i]);
    }
    auto it = s.begin();
    for (int i = 0; i < k - 1; i++) {
        it++;
    }
    return *it;
}

int main() {
    int arr[] = { 45, 32, 22, 23, 12 }, n = 5, k = 3;
    cout << findKthSmallestNumber(arr, n, k) << endl;
    return 0;
}

出力結果

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

23

処理の流れと計算量

この例では、配列 {45, 32, 22, 23, 12} の中から3番目に小さい要素を求めています。すべての要素をセットに挿入すると、セットの中身は自動的に {12, 22, 23, 32, 45} とソートされます。そのため、先頭から数えて3番目の要素である「23」が出力されます。

std::setは内部で平衡二分探索木（赤黒木）を使用しており、挿入1回あたりの計算量はO(log n)です。したがって、n個の要素を挿入する場合の全体の時間計算量はO(n log n)となります。また、重複する要素は自動的に除外される点にも注意してください。重複を許したい場合は、代わりにstd::multisetを使用します。

K番目に大きい要素を求めるには

K番目に大きい要素が必要な場合は、逆順イテレータ（rbegin）を使うだけで簡単に実現できます。

auto it = s.rbegin();
for (int i = 0; i < k - 1; i++) {
    it++;
}
return *it;

rbegin()はセットの最大要素を指すため、そこからk-1回進めると、k番目に大きい値が取得できます。

まとめ

本記事では、C++のSTLのstd::setを使用して、ソートされていない配列からK番目に小さい・大きい要素を求める方法を解説しました。セットの自動ソート機能を利用することで、コードがシンプルになり可読性も向上します。チュートリアルについてご不明な点がある場合は、コメント欄でお気軽にお尋ねください。