配列の最大値と最小値

n個の数値の配列が与えられます.nは偶数です。これらのn個の数値の最大値と最小値を決定する必要があります。必要な比較を知る必要がありますか？配列の最大値と最小値

出典

2013-03-14 user2170497

ヒント：3 * nの/ 2-2の比較が十分にあります。 – Henrik

@Henrikあなたは丁寧に教えてください。 – user2170497

O（n）時間で実行できます。

あなたはそれが3*n/2-2比較を使用して行うことができます参照

出典

2013-03-14 15:36:11

あなたは冗談でしょうか？ナイーブアプローチを使用すると、O（N） –

@IvayloStrandjevで行うことができます： - 私が間違っている場合は私を修正してください。しかし私はそれを2D配列と見なしました。 2D配列でもO（n）時間も可能ですか？ –

'n個の数字の配列が与えられます.nは偶数です。これらのn個の数字の最大値と最小値は決定される必要があります。私はここで2Dについて言及していません。 OPは最小数の比較を使用してn個の数字のうち最小値と最大値を見つける方法を尋ねます –

ため、このlinkをチェックアウトすることができます。

n == 2については、単純に2つの数値を比較してください。最初のn-2の最小値と最大値があるとします。残りの2つの数値を比較し、大きい方を前の最大値と比較し、小さい方を前の最小値と比較してください。

出典

2013-03-14 15:39:47 Henrik

ソートされていない配列の場合、約1.5nの比較で行うことができます。配列の要素のペアを比較し、minとローカルmaxを格納することで、これを行うことができます。（ローカル）を見つけるにはn/2の比較を実行し、最小を見つけるにはn/2を実行しました。したがって、合計でnがこの段階にあります。

ここでは、最大と最小の地方を行き来し、グローバルな最大値と最小値を見つけることができます。これはまた、n/2の比較をとるでしょう。従ってn + n/2 = 1.5n。

配列がソートされている場合は、最低数は、位置N上の最も高い位置0であるとするので、あなたは、任意の比較なしでそれを見つけることができます - 1.

出典

2013-03-14 16:02:12 dreamcrash

答えて

関連する問題