2

が配列 A の長さでA[1...n-1]ある整数の配列が与えられます。 が与えられるように配列を作成します。配列 B には N-K+1 要素が含まれます。NBB[i] = min(A[i], A[i+1], ..., A[i+K-1])K

min-heaps Construct min-heap for k elements - O(k) を使用して問題を解決できます。次の要素ごとに、最初の要素を削除し、新しい要素を挿入してヒープ化します。

したがって、最悪の場合の時間 - O( (n-k+1)*k ) + O(k) スペース - O(k)

もっとうまくできるでしょうか？

4

1 に答える 1

1

OPのアルゴリズムで、高価な「heapify」手順をはるかに安価な「upheap」または「downheap」に変更すると、より良い結果が得られます。これにより、O（n * log（k））の時間計算量が増加します。

または、入力配列を反復処理し、各要素をサイズ'k'の最小キューに入れると、O（n）時間で実行できます。最小キューは、O（1）時間でfind-minを実行できるキューです。最小スタックのペアとして実装できます。詳細については、この回答を参照してください。

于 2012-06-22T15:49:01.507 に答える