C++で配列の上位k個の最大要素を元の順序で出力する方法

問題概要

この問題では、n個の要素からなる配列 arr[] が与えられます。目的は、配列の中で値の大きい方からk個の要素を取り出し、元の配列での登場順序どおりに出力することです。

ポイントは、単に値の大きい順に並べるのではなく、元のインデックスの順番を維持したまま表示するという点にあります。

入出力例

入力： arr[] = {5, 1, 3, 6, 2}, k = 2

出力： 5, 6

解説： 配列内で最も大きい2つの要素は「6」と「5」ですが、元の配列では「5」が「6」よりも先に現れるため、この順序で出力されます。

解法のアプローチ

この問題は、次の手順で解くことができます。

1. 元の配列 arr[] をコピーし、降順にソートした配列 decArray を作成します。
2. 元の配列を先頭から順に走査し、各要素が decArray の上位k個に含まれているかどうかを判定します。
3. 含まれていれば、その要素を元の順序のまま出力します。

こうすることで、値の大小関係を保ちつつ、元の配列での位置関係も崩さずにk個の最大要素を取得できます。

C++による実装例

以下は、上記の解法を実装したC++プログラムです。

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

// 要素が上位k個に含まれるかどうかを判定する関数
bool searchVal(int decArr[], int k, int ele){
    for(int i = 0; i < k; i++){
        if(decArr[i] == ele)
            return true;
    }
    return false;
}

// 元の順序でk個の最大要素を出力する関数
void printKMaxEle(int arr[], int k, int n) {
    // 配列をコピーして降順にソート
    int decArr[n];
    for(int i = 0; i < n ; i++){
        decArr[i] = arr[i];
    }
    sort(decArr, decArr + n, greater<int>());

    // 元の配列を走査し、上位k個に含まれる要素を出力
    for (int i = 0; i < n; ++i)
        if (searchVal(decArr, k, arr[i]))
            cout<<arr[i]<<" ";
}

int main() {
    int arr[] = { 15, 1, 3, 6, 2, 34, 8, 9 };
    int n = sizeof(arr) / sizeof(arr[0]);
    int k = 3;
    cout<<k<<" 個の最大要素（元の順序）：\n";
    printKMaxEle(arr, k, n);
    return 0;
}

実行結果

3 個の最大要素（元の順序）：
15 34 9

計算量の目安

この実装では、降順ソートに O(n log n) の計算量が必要です。さらに、元の配列の各要素について上位k個との照合（線形探索）を行うため、照合部分は O(n × k) の計算量になります。

要素数が多い場合は、unordered_set を使って上位k個の値を事前に格納しておくことで、照合処理を平均 O(1) に高速化でき、全体的なパフォーマンスを向上させることが可能です。