配列内で 2 番目に大きい要素を見つけるための C++ プログラム

配列の目的は、ベース アドレスとインデックスを使用してアクセスできる一連のメモリ位置に、同様のタイプのデータを格納することです。私たちはさまざまなアプリケーションで配列を使用して、さまざまな目的でデータを保持します。最小要素と最大要素の検索は配列の非常に一般的な例であり、並べ替えなどのいくつかのアプリケーションで必要となります。この記事では、C で配列から 2 番目に大きい要素を見つける方法を学びます。

例を通じて概念を理解する

リーリー

上記の例では、配列には 12 個の要素があります。配列内の最大の要素は 99 で、2 番目に大きい要素は 89 です。最初の方法では、2 番目に大きい要素を見つけるには、要素を昇順または降順に並べ替えて、最後から 2 番目または 2 番目の要素を直接返して 2 番目に大きい要素を取得するだけです。アルゴリズムは次のとおりです -

＃＃＃アルゴリズム＃＃＃

サイズ n の配列 A

• を取得します

配列Aを配列Aの値の非増加順に並べ替えます
Return A[ 1 ] // 0 番目のインデックスに最大の要素が含まれるため

• ＃＃＃例＃＃＃ リーリー ＃＃＃出力＃＃＃ リーリー
ダブルトラバーサルを使用する

上記の方法は簡単に見えますが、このプロセスはこの問題に対して効率的ではありません。並べ替えを使用しているため、並べ替えの実行には少なくとも O(n.log n) 時間がかかります。しかし、この問題は線形時間で解決することもできます。現在のメソッドでは、要素の配列を 2 回繰り返し、2 番目に大きい要素を見つけます。アルゴリズムを確認してみましょう。

＃＃＃アルゴリズム＃＃＃

サイズ n の配列 A

を取得します

最大値:= -無限大

• 最大秒数:= -infinity

• A の要素 e ごとに、

  を実行します。

• e が最大値より大きい場合、

• 最大=e

  • 終了場合

    • ＃＃＃＃＃＃＃＃＃仕上げる＃＃＃＃＃＃
    A の要素 e ごとに、
  を実行します。

  • e が secLargest より大きく、最大値より小さい場合、
• 2 番目の最大値 = e

• 終了場合

  • ＃＃＃＃＃＃＃＃＃仕上げる＃＃＃＃＃＃

    最大秒数を返します

    • ＃＃＃例＃＃＃ リーリー ＃＃＃出力＃＃＃ リーリー
    単一トラバーサルを使用する
  上記の解決策は、配列を 2 回繰り返します。最初の実行では、配列から最大の要素を検索し、次に 2 回目の実行では、最初の最大の要素以下の最大の要素を検索します。配列は線形データ構造であるため、各走査には O(n) 時間がかかり、最終的な解決時間は O(2n) となり、これも O(n) と同様に線形です。しかし、これは効率的な解決策ではありません。この問題は 1 回のパスでしか解決できません。そのアルゴリズムを見てみましょう。
  • ＃＃＃アルゴリズム＃＃＃

  サイズ n の配列 A
を取得します

• 最大値:= A[0]

• 1 から n - 1 までのインデックスを開始するには、

  を実行します。

現在の要素 A[i] が最大値より大きい場合、

2 番目の最大値 := 最大値

最大値:= A[ i ]

それ以外の場合、A[ i ] が最大値と秒最大値の間にある場合、
最大秒数 := A[ i ]

• • 終了場合

    • ＃＃＃＃＃＃＃＃＃仕上げる＃＃＃＃＃＃
      最大秒数を返します

    • ＃＃＃例＃＃＃ リーリー ＃＃＃出力＃＃＃ リーリー ＃＃＃結論は＃＃＃

      この記事では、指定された配列から 2 番目に大きい要素を見つける 3 つの異なる方法について学びました。 1 つ目の方法は、並べ替えを使用することです。ただし、この解決策は効率的ではなく、少なくとも O(n log n ) 時間がかかります。後者の解決策は線形時間を必要とするため、非常に効率的です。 2 番目の解決策は、配列に対してダブル パスを使用することです。これは、3 番目の解決策に示すように、シングル パスで最適化することもできます。

以上が配列内で 2 番目に大きい要素を見つけるための C++ プログラムの詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。