計算量の制約を満たしながらn個の要素から2番目に小さい値を見つけるC++プログラム

本記事では、指定された計算量の制約（O(n)の1回走査）を満たしながら、n個の要素の中から2番目に小さい値を見つけるC++プログラムを紹介します。

配列をソートする方法（O(n log n)）もありますが、ここで紹介するアルゴリズムは配列を一度だけ走査すればよいため、より効率的です。

アルゴリズム

Begin
    function SecondSmallest() :
      /* この関数の引数：
         配列へのポインタ a
         要素数 n
      */
    // 関数の処理内容：
        最小値を追跡するための変数 s1 を宣言
        2番目に小さい値を追跡するための変数 s2 を宣言
        s1 と s2 を両方とも INT_MAX で初期化
        反復処理によってデータ配列を走査する
        現在の配列要素が s1 の現在値より小さい場合、
            s2 = s1 とし、s1 = 現在の配列要素とする
        そうでなく、配列要素が s1 と s2 の間にある場合、
            s2 = 現在の配列要素とする
        if(s2 == INT_MAX)
            「2番目に小さい要素は存在しない」と出力
        else
            s2 を2番目に小さい要素として出力
End

ポイント解説

• s1：これまでに見つかった最小値を保持します。
• s2：これまでに見つかった2番目に小さい値を保持します。
• 新しい要素が s1 より小さければ、旧 s1 の値は s2 へ繰り下げられます。
• 要素が s1 と s2 の間にあれば、s2 だけを更新します。このとき a[i] != s1 の条件により、重複した最小値が誤って s2 に入ることを防いでいます。

サンプルコード

#include<iostream>
#include <climits> // INT_MAX を使用するため
using namespace std;

int SecondSmallest(int *a, int n) {
    int s1, s2, i, t;
    // s1 と s2 を初期化
    s1 = INT_MAX;
    s2 = INT_MAX;

    for(i = 0; i < n; i++) {
        // 現在の要素が s1 より小さい場合
        if(s1 > a[i]) {
            // s1 と s2 を更新
            s2 = s1;
            s1 = a[i];
        }
        // a[i] が s1 と s2 の間にある場合
        else if(s2 > a[i] && a[i] != s1) {
            // s2 のみ更新
            s2 = a[i];
        }
    }

    if(s2 == INT_MAX)
        cout << "no second smallest element is present";
    else
        cout << "Second smallest element is:" << s2;
}

int main() {
    int n, i;
    cout << "Enter the number of elements: ";
    cin >> n;

    int array[n];
    for(i = 0; i < n; i++) {
        cout << "Enter " << i+1 << " " << "element: ";
        cin >> array[i];
    }

    SecondSmallest(array, n); // 関数を呼び出す
    return 0;
}

実行結果

Enter the number of elements: 5
Enter 1 element: 1
Enter 2 element: 2
Enter 3 element: 1
Enter 4 element: 3
Enter 5 element: 4
Second smallest element is:2

まとめ

このプログラムは、配列を一度だけ走査して最小値と2番目に小さい値を同時に求めるため、時間計算量は O(n)、空間計算量は O(1) となります。入力例のように重複した値（1が2回出現）が含まれていても、正しく「2」を2番目に小さい要素として判定できる点が特徴です。