最高の数字を見つける

数百万の整数が与えられています。これから最大の数字を見つけるには？入力が巨大なのでメモリには何も格納できません。最高の数字を見つける

提案がありますか？

おかげであなたが（例えば一つのメディアの1からそれらを読んで）すべての数字を反復処理し、唯一の10個の最大の番号のリストを維持することができます

出典

2012-02-13 Shags

「n」の大きさはどれくらいですか？すべての結果をメモリに保存するには十分ですか？ – millimoose

最大==最大？ – shift66

いくつかのコードを表示してください。 –

をシャグ。擬似コードで

：

max_numbers = new int[n] 
until not end of file: 
    read number 
    if number > min(max_numbers): 
     'copy number to minimum value of max_numbers'

出典

2012-02-13 13:20:22

-1

EDITED

私はそれにマイケルの提案を服用すると、論理的な結論ですが、プライオリティキュー（ヒープベース）を形成するお勧めします。 10を保管しないでください。

PQ a[n]; 
a.insert(input);

O(log n) FTW

出典

2012-02-13 13:20:24

いいえ、ヒープはO（N lg n）の答えを返します。ここで、Nは数百万になります。また、この作業には[min-heap]（http://stackoverflow.com/a/9118787/166749）が必要です。 –

ヒープをあらかじめ決められた最大深度だけに変更していない限り、すべての入力をメモリに保持する必要があります。私はこれがウィキペディアのリンクをあまりにも曖昧にして助けにならないと主張するだろう。 – millimoose

私の答えが変更されました。レビューしてください。 –

あなたは数字を介して実行しながら、10の長さの配列を取得し、新しい大きなで最小を交換。

出典

2012-02-13 13:23:37 sinsedrix

public void largest() { 
    int _current, _highest, _lowest; 

    if(_current >= _highest) { 
     _highest = _current; 
    } else if(_current <= _lowest) { 
     _lowest = _current; 
    } 
}

私は何をしますか？

出典

2012-02-13 13:49:24

サイズnのMax-Heapを維持します。

出典

2012-02-13 14:35:36 Bhushan

これは動作しますが、Nlog（N）で実行されますが、理想的な解決策はN時間で実行できます。 – zzz

@エリック：説明していただけますか？ – Bhushan

ちょうどn個の要素の配列を持っていて、配列内で最小のものより大きいものを見つけたら、それを変更することができます。

何かを変更する必要があることがわかっているときに、配列の最小番号を保持しておくと、追加の変数を保持することができます。

出典

2012-11-13 22:42:50 chamini2

答えて

関連する問題