C++でソートされていない整数配列から最大値と2番目に大きい値を見つけるプログラム

問題の概要

サイズNのソートされていない整数配列が与えられたとします。この課題は、配列内に存在する重複を除いた最大値と2番目に大きい値を見つけることです。配列には同じ要素が複数含まれる場合があるため、重複を除外した値だけを対象にしなければなりません。

具体例を見てみましょう。

入力1 −

N = 5
A[ ] = { 2, 2, 1, 3, 4 }

出力 −

4 3

説明 − 与えられた配列から、「4」が最大値、「3」が2番目に大きい値であることがわかります。

入力2 −

N = 4
A[ ] = { 1, 3, 3, 2 }

出力 −

3 2

説明 − サイズ4の配列において、「3」が最大値、「2」が2番目に大きい値であるため、「3 2」を出力として返します。

この問題を解くためのアプローチ

サイズNの配列には重複した要素が含まれている可能性があります。最大値と2番目に大きい値を見つけるには、それぞれを格納するための2つの変数を用意するのが基本的な考え方です。

まず、現在の要素が最大値より大きい場合、その値を新しい最大値として保存し、それまでの最大値を2番目に大きい値へと繰り下げます。

重複を除外するために、現在の要素が最大値と等しいかどうかを必ず確認します。現在の値が最大値と等しくなく、かつ2番目に大きい値より大きい場合にのみ、2番目に大きい値を現在の値で置き換えます。

アルゴリズムの手順

• 配列のサイズNと配列の要素を入力として受け取ります。

• 関数 maxAndSecondMax(int arr[], int size) は、配列とそのサイズを引数として受け取り、配列内の最大値と2番目に大きい値を返します。

• 配列の要素を先頭から走査し、現在の要素が最大値より大きい場合は、現在の値を最大値に、それまでの最大値を2番目に大きい値に保存します。

• それ以外の場合、現在の値が2番目に大きい値より大きく、かつ最大値と等しくないときは、2番目に大きい値を現在の値で更新します。

• 2番目に大きい値が一度も更新されていない(該当する値が存在しない)場合は、その旨をチェックします。

• 最大値と2番目に大きい値を最終的な出力として返します。

実装例

#include<bits/stdc++.h>
using namespace std;
void maxAndSecondMax(int *arr, int size){
    int max= INT_MIN;
    int s_max= INT_MIN;
    for(int i=0;i<size; ++i){
        if(arr[i] >max){
            s_max= max;
            max= arr[i];
        }
        else if(arr[i]> s_max && arr[i]!= max){
            s_max= arr[i];
        }
    }
    if(s_max==INT_MIN){
        s_max= -1;
    }
    cout<<max<<" "<<s_max;
}
int main(){
    int N= 6;
    int A[N]= {1,3,2,5,6,3};
    maxAndSecondMax(A,N);
    return 0;
}

出力

上記のコードを実行すると、次の出力が表示されます。

6 5

6と5は、配列内の重複を除いた要素の中で、それぞれ最大値と2番目に大きい値に該当します。

このアルゴリズムは配列を一度だけ走査するため、計算量はO(N)、追加のメモリはO(1)で済み、非常に効率的です。配列をソートする方法(O(N log N))よりも高速に動作する点が大きなメリットといえます。