C++プログラムで配列の最小・2番目・3番目に小さい要素を効率よく見つける方法

はじめに

n個の要素からなる配列が与えられたとき、その中から最小の要素(第1最小値)、2番目に小さい要素(第2最小値)、3番目に小さい要素(第3最小値)を見つける方法を解説します。ここで「2番目に小さい要素」とは、最小値より大きい値の中で最も小さいものを指し、「3番目に小さい要素」は2番目に小さい値より大きい値の中で最も小さいものを指します。

アルゴリズムの考え方

配列の各要素を先頭から順に走査し、それぞれの要素について以下の3つの条件を順番にチェックすることで、この問題を解くことができます。

• 要素が現在の最小値(first)より小さい場合:3番目の値に2番目の値を、2番目の値に最小値を順にずらし、その要素を新しい最小値として更新します。
• 要素が2番目に小さい値(sec)より小さい場合:3番目の値に2番目の値をずらし、その要素を新しい2番目の値として更新します。
• 要素が3番目に小さい値(third)より小さい場合:その要素を新しい3番目の値として更新します。

この手法を用いれば、配列をたった1回走査するだけで(計算量 O(n))、3つの最小値を同時に求めることができます。ソートを行う必要がないため、非常に効率的です。

サンプルコード

#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

まとめ

このプログラムでは、3つの変数(first、sec、third)を INT_MAX で初期化し、配列を1回走査するだけで最小・2番目・3番目に小さい要素を求めています。配列の要素数が3未満の場合は値が INT_MAX のまま残るため、実務ではそのケースへのチェックを追加するとより堅牢なコードになります。