1

O（n）時間計算量の中央値の中央値アルゴリズムを使用して、n番目に大きいものを簡単に見つけることができます。 同じ配列でn番目に大きい数を複数回見つける必要がある場合は、O（NlogN）を並べ替えてから、 O（1）の時間計算量 で数を見つけるのが最善です。 しかし、配列サイズが大きくなり、 array.length /3番目に大きいまたはarray.length/2番目に大きいなど、n番目に大きい数を見つける必要がある場合の効率的なアルゴリズムは何でしょうか。例



Array- 1,3,2,4,5 n=2 Answer-4   
New Array 1,3,2,4,5,7  n=2 answer-5  
New Array 1,3,2,4,5,7,3 n=2 answer-5


nは配列の長さに依存することに注意してください。
助けてください。

4

2 に答える 2

7

アレイ全体を常に追跡する必要があると私は確信しています。100、99、98、...、1、0、-1、...を受け取ったとすると、n番目に大きい数は、速度は低下しますが、同じシーケンスに従います：100、100、99、99、98、 98..。

基本的に、入力からの数値を忘れることはできません。このシナリオでは、各数値が最終的にn番目に大きい数値として選択されるためです。

とは言うものの、新しい要素を読み込むたびにn番目に大きい要素を「更新」するO（log N）アルゴリズム（Nの場合は全体の要素数）があります。これはおそらく最適と思われます。多かれ少なかれ、n個の最大の要素の最小優先度キューとNn個の小さい要素の最大優先度キューを保持するだけです。nが増加するたびに（たとえば、array.length / 3が増加する）、小さい要素のキューから大きい要素のキューに何かを引き出します。新しい要素を読み取るたびに、それを適切なキューに入れ、「大きい要素」のキューから「小さい要素」のキューに要素を追加する可能性があります。

于 2012-07-09T10:24:37.830 に答える
0

興味深い問題。これは、一意の値の数と、新しい配列、検索、および挿入から開始する頻度によって異なります。

nの多くが一意であり、挿入/検索が頻繁に行われる新しい配列から開始することはめったにありませんが、私の最初の勘は次のようになります。

  • tipmax-heapとmax-heapを作成し、bulknを目的のランク（n番目の値）とします。
  • 挿入：新しいノードをtip;にプッシュします。の場合tip.size() >= (n-1)、ポップtip.top()して押し込みますbulk
  • 検索：戻るbulk.top()

これO(N log(N))により、起動、O(log(N))挿入（並べ替えよりもはるかに高速）、およびO(1)検索が可能になります。

一意の値の数がNよりもはるかに少ない場合は、おそらくカウントソートを使用してから、ビンを値でソートします。

編集：ルイ・ワッサーマンの答えをもう少し詳しく見ると、それは私の最初のアルゴリズムとほぼ完全に重複しているようです。ただし、「小さい要素のキューから何かを引き出す」代わりに、最大要素を最小ヒープにプッシュする要素として選択することで、検索O（1）を実行できることをお勧めします。

于 2012-07-09T19:15:00.907 に答える