4

並べ替えられていない配列が与えられ、効率的な方法で上位 5 つの要素を見つける必要があり、リストを並べ替えることができません。

私の解決策：

  • 配列内の最大要素を見つけます。の上）

  • この max 要素は、処理/使用後に削除してください。

  • ステップ 1 と 2 を k 回 (この場合は 5 回) 繰り返します。

時間の複雑さ: O(kn) / O(n)、空間の複雑さ: O(1) .

O(logN) で最大要素を見つけることができると思うので、O(klogN)に改善できます。間違っている場合は修正してください。

これよりもうまくできるでしょうか？max-heap を使用すると効率が悪いのではないでしょうか?

PS - これは宿題ではありません。

4

2 に答える 2

8

補助ヒープ (マイナス要素が一番上にある最小ヒープ) を使用できるO(nlogm)場合nは、リストの長さとm追跡する最大要素数です。

補助ヒープは最大サイズ(5)が決まっているので、その構造に対する操作は考えられると思いますO(1)。その場合、複雑さはO(n)です。

擬似コード:

foreach element in list:
    if aux_heap.size() < 5  
        aux_heap.add(element)
    else if element > aux_heap.top()
        aux_heap.remove_top()
        aux_head.add(element)
于 2012-08-17T18:45:32.180 に答える
4

部分的なクイックソートを使用すると、O(n) を実現できます。これには補助スペースは必要ありません。他のソリューションと同様に、最大ヒープを使用するには O(n log k) の時間が必要です。

于 2012-08-17T18:47:49.433 に答える