C++で配列内の最小値・2番目・3番目に小さい要素を効率的に見つける方法

n個の要素からなる配列が与えられたとき、その中から「1番目（最小）」「2番目」「3番目」に小さい要素を求めることを考えます。ここで、1番目の最小値は配列全体の最小値、2番目の最小値は1番目より大きい値の中で最も小さいもの、3番目の最小値は2番目より大きい値の中で最も小さいものを指します。

この問題は、配列を一度だけ走査しながら、各要素について「1番目・2番目・3番目の最小値」の条件を順に判定していくことで解くことができます。

アルゴリズムの考え方

まず、1番目・2番目・3番目の最小値を表す変数 first、sec、third を用意し、それぞれ int 型の最大値 INT_MAX で初期化します。次に、配列の各要素 arr[i] に対して以下の判定を行います。

• arr[i] が first より小さい場合：third に sec の値を、sec に first の値を移し、first を arr[i] で更新します。
• arr[i] が sec より小さい場合：third に sec の値を移し、sec を arr[i] で更新します。
• arr[i] が third より小さい場合：third を arr[i] で更新します。

この処理により、配列を1回走査するだけで3つの最小値を同時に求められます。時間計算量は O(n)、空間計算量は O(1) と非常に効率的です。

サンプルコード

#include<iostream>
using namespace std;
int getThreeMins(int arr[], int n) {
    int first = INT_MAX, sec = INT_MAX, third = INT_MAX;
    for (int i = 0; i < n; i++) {
        if (arr[i] < first) {
            third = sec;
            sec = first;
            first = arr[i];
        } else if (arr[i] < sec) {
            third = sec;
            sec = arr[i];
        } else if (arr[i] < third)
            third = arr[i];
    }
    cout << "First min = " << first << endl;
    cout << "Second min = " << sec << endl;
    cout << "Third min = " << third << endl;
}
int main() {
    int array[] = {4, 9, 18, 32, 12};
    int n = sizeof(array) / sizeof(array[0]);
    getThreeMins(array, n);
}

実行結果

First min = 4
Second min = 9
Third min = 12

動作の解説

この例では、配列 {4, 9, 18, 32, 12} を先頭から順に処理していきます。

• 4 は INT_MAX より小さいため、first = 4 となります。
• 9 は first(4) より大きいですが sec(INT_MAX) より小さいため、sec = 9 となります。
• 18、32 はいずれの条件にも当てはまりません。
• 12 は sec(9) より大きく third(INT_MAX) より小さいため、third = 12 となります。

最終的に、最小値は 4、2番目に小さい値は 9、3番目に小さい値は 12 として出力されます。

注意点

このアルゴリズムでは重複した値も別々の要素として扱われます。たとえば配列に {4, 4, 9} が含まれる場合、2番目の最小値は 4 になります。もし「異なる値」として扱いたい場合は、比較条件に等号を含めるなどの工夫が必要です。また、配列の要素数が3未満の場合、INT_MAX のまま残る値が出力されるため、実用時には要素数のチェックを追加することをおすすめします。