0

以下の条件で、配列内の最大値と最小値の 2 つを見つけるために Java コードを記述する必要がある問題を解決しようとしています。

・すべての要素が実数

-すべての要素はランダムです

最善のアプローチに関するアイデアはありますか？

4

4 に答える 4

6

すべての数値を調べる必要があるため、最良のアルゴリズムは配列の長さに対して線形です。

標準的なアプローチは、配列をスキャンして、これまでに見た最小と最大の 2 つの数値を追跡することです。

したがって、firstMin、secondMin、firstMaxがsecondMaxそれぞれこれまでに見た中で最小、2 番目に小さい、最大、2 番目に大きい値であるとすると、ループの次の繰り返しでは:

if (value > firstMax) {
    secondMax = firstMax;
    firstMax = value;
} 
else if (value > secondMax) {
    secondMax = value;
}

if (value < firstMin) {
    secondMin = firstMin; 
    firstMin = value;
}
else if (value < secondMin) {
    secondMin = value;
}

このブロックの最後でfirstMin、secondMin、firstMax、secondMaxがそれぞれこれまでに見た最小値、2 番目に小さい値、最大値、2 番目に大きい値であるという不変条件を維持します。これは正しさを証明します。

このアルゴリズムは、配列の長さに関して線形であり、各値を 1 回だけ検査し、最小数の比較を行います。これはO(1)スペース内にもあり、上位 2 つの値と下位 2 つの値に対して 4 つの余分なメモリ ロケーションのみを使用するという点で最適です。

于 2013-07-18T00:37:33.193 に答える
5

これまでに確認した min、second_min、max、および second_max の値を追跡するための変数を用意します。

配列の要素を 1 つずつ確認し、それに応じて最小/最大変数を更新できます。考慮すべきいくつかのケースを次に示します。

  • 現在の要素が最小値より小さい場合は、最小値を second_min に保存して最小値を更新します。
  • 現在の要素が最大値より大きい場合、最大値を second_max に保存して最大値を更新します
  • 現在の要素が second_min より小さいが、min より大きい場合は、second_min のみを更新します
  • 現在の要素が second_max よりも大きいが max よりも小さい場合、second_max のみを更新します
于 2013-07-18T00:38:05.993 に答える