C++で配列内の最大3つの要素を検索する方法

この記事では、ソートされていない N 個の要素からなる配列 arr[] が与えられたときに、配列内で最も大きい3つの要素を見つける方法を解説します。

問題の例

まず、具体例を使って問題を確認しましょう。

入力 : arr[] = {7, 3, 9, 12, 1}
出力 : 12, 9, 7

解決アプローチ

求めるのは「配列の中で最大の3つの要素を見つけて出力する」ことです。これを実現する方法は複数あります。

方法1：一度の走査で上位3要素を追跡する（O(n)）

最大の3つの要素の値を保持するために、max、max2、max3 という3つの変数を用意し、すべて arr[0] で初期化します。

続いて、配列を先頭から末尾まで走査しながら、各要素に対して以下の判定を行います。

• if (arr[i] > max) → max3 = max2、max2 = max、max = arr[i]
• else if (arr[i] > max2) → max3 = max2、max2 = arr[i]
• else if (arr[i] > max3) → max3 = arr[i]

ループが終了した時点で、3つの変数に格納された値を出力します。

この方法のメリットは、配列をたった1回の走査（O(n)）で処理できる点です。追加のメモリも定数個の変数だけで済むため、大規模な配列でも効率的に動作します。

サンプルプログラム（方法1）

#include <iostream>
using namespace std;
void findThreeLargestElements(int arr[], int arr_size){
    int max, max2, max3;
    max3 = max = max2 = arr[0];
    for(int i = 0; i < arr_size; i++){
        if (arr[i] > max){
            max3 = max2;
            max2 = max;
            max = arr[i];
        }
        else if (arr[i] > max2){
            max3 = max2;
            max2 = arr[i];
        }
        else if (arr[i] > max3)
            max3 = arr[i];
    }
    cout<<endl<<"Three largest elements of the array are "<<max<<", "<<max2<<", "<<max3;
}
int main(){
    int arr[] = {15, 2, 7, 86, 0, 21, 50};
    int n = sizeof(arr) / sizeof(arr[0]); 
    cout<<"The array is : ";
    for(int i = 0; i < n; i++) 
        cout<<arr[i]<<"\t"; 
    findThreeLargestElements(arr, n);
    return 0;
}

実行結果

The array is : 15 2 7 86 0 21 50
Three largest elements of the array are 86, 50, 21

方法2：ソートを利用する（O(n log n)）

もうひとつのシンプルな解決策は、配列を降順にソートしてから、先頭の3つの要素を出力する方法です。降順ソート後の先頭3要素が、そのまま配列内で最大の3つの要素になります。

アルゴリズム

• ステップ1 − ソートアルゴリズムを使って配列を降順にソートします。
• ステップ2 − 先頭の3つの要素 arr[0]、arr[1]、arr[2] を出力します。

なお、重複した値を除外したい場合は、直前の出力値と比較しながら異なる値だけを3つ出力するとよいでしょう。

サンプルプログラム（方法2）

#include <bits/stdc++.h>
using namespace std;
void findThreeLargestElements(int arr[], int n){
    sort(arr, arr + n, std::greater<>());
    int j = 0;
    cout<<"\nThree largest elements are ";
    for(int i = 0; i < n; i++){ 
        if(arr[i] != arr[i+1]){ 
            cout<<arr[i]<<" "; 
            j++;
        }
        if(j == 3){
            break;
        }
    }
}
int main(){
    int arr[] = {15, 2, 7, 86, 0, 21, 50, 53, 50};
    int n = sizeof(arr) / sizeof(arr[0]);
    cout<<"The array is : ";
    for(int i = 0; i < n; i++)
        cout<<arr[i]<<"\t";
    findThreeLargestElements(arr, n);
    return 0;
}

実行結果

The array is : 15 2 7 86 0 21 50 53 50
Three largest elements are 86 53 50

まとめ

パフォーマンスを重視する場合は方法1を、コードの簡潔さを優先する場合は方法2を選ぶとよいでしょう。