配列内のK番目に大きい要素を求めるアルゴリズム

このアルゴリズムは、与えられたデータ集合の中から、配列の最大要素からK番目に大きい要素までを見つけ出すものです。

この問題は、配列をソートすることで簡単に解決できます。ソートは昇順・降順のどちらでも構いませんが、降順に並べ替えれば、先頭のK個の要素を取り出すだけで目的の結果が得られます。

入力と出力

入力:
配列の要素: {1, 23, 12, 9, 30, 2, 50, 63, 87, 12, 45, 21}, K = 4

出力:
4つの大きい要素: 87 63 50 45

アルゴリズム

kthLargestElement(array, n, k)

入力: 配列、配列の要素数 n、順位 k

出力: 最大要素からK番目に大きい要素までを表示する

擬似コード

Begin
    配列を降順にソートする
    for i := 0 to k-1, do
        array[i] を表示する
    done
End

C++による実装例

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

bool compare(int a, int b) {
    return a>b;
}

void kthLargestElement(int array[], int n, int k) {
    sort(array, array+n, compare);

    for (int i = 0; i < k; i++)     // 最大値からK番目に大きい要素まで表示
        cout << array[i] << " ";
}

int main() {
    int array[] = {1, 23, 12, 9, 30, 2, 50, 63, 87, 12, 45, 21};
    int n = 12;
    int k = 4;
    kthLargestElement(array, n, k);
}

実行結果

87 63 50 45

計算量の目安

この手法では、ソートに O(n log n)、上位K個の表示に O(K) の時間がかかるため、全体の時間計算量は O(n log n) となります。より効率的に求めたい場合は、優先度付きキュー（ヒープ）を活用する方法や、平均 O(n) で動作するクイックセレクトを採用するのも有効です。