C++でソートされていない配列からK番目に小さい・大きい要素を求める方法

このチュートリアルでは、ソートされていない配列の中からk番目に小さい数値、およびk番目に大きい数値を見つけるプログラムをC++で作成する方法を解説します。

アルゴリズムの手順

問題を解くための基本的な流れは以下の通りです。

1. 配列とkの値を初期化します。
2. sort関数を使って配列を昇順にソートします。
3. インデックス k - 1 の要素を返します。

サンプルコード：k番目に小さい要素

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

#include <bits/stdc++.h>
using namespace std;
int findKthSmallestNumber(int arr[], int n, int k) {
    sort(arr, arr + n);
    return arr[k - 1];
}
int main() {
    int arr[] = { 45, 32, 22, 23, 12 }, n = 5, k = 3;
    cout << findKthSmallestNumber(arr, n, k) << endl;
    return 0;
}

実行結果

上記のコードを実行すると、次の出力が得られます。

23

配列を昇順にソートすると { 12, 22, 23, 32, 45 } となるため、3番目に小さい要素は 23 です。

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

k番目に大きい要素が必要な場合は、昇順ソート後のインデックス n - k の要素を取得すればOKです。

#include <bits/stdc++.h>
using namespace std;
int findKthLargestNumber(int arr[], int n, int k) {
    sort(arr, arr + n);
    return arr[n - k];
}
int main() {
    int arr[] = { 45, 32, 22, 23, 12 }, n = 5, k = 3;
    cout << findKthLargestNumber(arr, n, k) << endl;
    return 0;
}

降順に並べると { 45, 32, 23, 22, 12 } なので、3番目に大きい要素も 23 となります。

計算量とより効率的な方法

sort を使う場合の時間計算量は O(n log n) です。もし部分ソートで十分な場合は、標準ライブラリの std::nth_element を使うと、平均 O(n) でk番目の要素を求められます。

#include <bits/stdc++.h>
using namespace std;
int main() {
    int arr[] = { 45, 32, 22, 23, 12 }, n = 5, k = 3;
    nth_element(arr, arr + k - 1, arr + n);
    cout << arr[k - 1] << endl;
    return 0;
}

nth_element は、指定した位置（ここでは arr + k - 1）に「その位置にあるべき要素」を配置してくれる便利な関数です。配列全体を完全にソートする必要がないため、高速に動作します。

まとめ

本記事では、C++でソートされていない配列からk番目に小さい・大きい要素を求める方法を紹介しました。シンプルなのは sort を使う方法、パフォーマンスを重視するなら nth_element を使う方法がおすすめです。チュートリアルについて質問がある場合は、コメント欄でお気軽にお知らせください。