C++で「自分より大きい要素が2つ以上ある」配列内のすべての要素を検索する方法

問題の概要

n個の数値で構成される配列が与えられたとき、「自分自身より大きい要素が少なくとも2つ存在する」すべての要素を見つけることを考えます。

例えば、配列が A = [2, 8, 7, 1, 5] の場合、結果は [2, 1, 5] となります。これらの要素には、それぞれ2つ以上のより大きな要素が配列内に存在するためです。

解決のアプローチ

この問題は、配列を2回走査するだけで効率的に解くことができます。

1. 1回目の走査で、配列の最大値(first_max)と2番目に大きい値(second_max)を求めます。
2. 2回目の走査で、second_maxより小さいすべての要素を出力します。

この方法の時間計算量は O(n)、追加で必要なメモリは O(1) と非常に効率的です。

サンプルコード(C++)

#include<iostream>
using namespace std;
void searchElements(int arr[], int n) {
   int first_max = INT_MIN, second_max = INT_MIN;
   for (int i = 0; i < n; i++) {
      if (arr[i] > first_max) {
         second_max = first_max;
         first_max = arr[i];
      } else if (arr[i] > second_max)
         second_max = arr[i];
   }
   for (int i = 0; i < n; i++)
   if (arr[i] < second_max)
   cout << arr[i] << " ";
}
int main() {
   int arr[] = { 2, 9, 1, 7, 5, 3, 17};
   int n = sizeof(arr) / sizeof(arr[0]);
   cout << "Elements are: ";
   searchElements(arr, n);
}

実行結果

Elements are: 2 1 7 5 3

コードの解説

searchElements関数では、まず1回目のループで最大値と2番目に大きい値を追跡します。現在の要素がfirst_maxより大きい場合は、first_maxの値をsecond_maxに退避させてからfirst_maxを更新します。そうでなくsecond_maxより大きい場合は、second_maxだけを更新します。

続く2回目のループでは、second_maxより厳密に小さい要素のみを出力します。上記の例では、最大値が17、2番目に大きい値が9であるため、9より小さい「2 1 7 5 3」が出力されます。