1

次の質問があります。

整数の配列 A と、オーバーラップしていないt 個のセクション [L1,R1],[L2,R2]...[Lt,Rt]が与えられた場合

すべてのセクションが配列 (A) の開始インデックス (Li) と終了インデックス (Ri) であるように、

O(t + klogk) の複雑さで、これらのセクション (インデックスはセクションにあり、要素は配列 A にあります) から上位 k 要素を返すデータ構造を見つけます。

ヘルパーのAvihaiに感謝します。

4

2 に答える 2

1

問題の言い回しは少しあいまいです。複雑に実行される操作の一部として何を数えますO(t+klogk)か?

これに答えるには3つのオプションがあります。最初の 2 つは、元の質問を解釈するには間違っていると思いますが、回答を提示します。3 番目と最後のオプションについては、解決策がありません。それでも、質問を明確にし、最初の 2 つに私の回答を追加する必要があると思いました。さらに、この問題に関する長い議論をコメントに追加することは、不可能ではないにしても混乱を招きます.

私が始めた質問に答えるために私が見るオプションは次のとおりです。

オプション 1 - データ構造の構築 (セクションを使用) 含まない

A元の質問の現在の言い回しから、問題は配列とセクションを使用して事前に構築できるデータ構造を要求しているように聞こえます[L1,R1],[L2,R2],...,[Lt,Rt]。複雑さの要件で考慮される唯一の操作は、抽出するデータ構造で行われる操作です。最高k値。

tこの場合、なぜ複雑になるのかが不明なので、あまり意味がありません。コメントでフアンの回答にリンクしたこの回答から、データ構造から最高値の要素を取得O(klogk)するために取得できる関連要素のみを使用して事前にヒープを構築することにより、(存在する場合)ことがわかります。k

オプション 2 - 含まれるすべての操作

問題が複雑さの要件のために考慮される操作の一部としてデータ構造を構築することを要求しているかのようにそれを読んだ場合 (配列とインデックスのリストのみを取得し、それを処理する必要があり[L1,R1,L2,R2,...,Lt,Rt]ます)、複雑さの要件はありません。達成可能。データ構造を構築したい場合は、少なくともデータ構造に挿入する必要があるすべての要素を確認する必要があります。データ構造を構築したくない場合は、配列をそのまま使用するつもりです。次に、最大値を見つけるために必要なすべての要素を調べる必要があります。いずれにせよ、配列内の要素の数を取得t=1し、L1=1, R1=nどこにある場合は、すべての要素を調べる必要がありますnAAA（ 「要素」の順序に関する仮定はありません）。つまり、少なくとも が必要でO(n)、要件はO(t+klogk)です。これらがまったく無関係な量であることをさらに明確にするために、任意の長さ (10,000 としましょう) を持つことができるk=1一方で、最高の要素のみを見つけることを意味するの場合を考えることができます。A

オプション 3 - 配列を除外したデータ構造ビルドのみ

これにより、質問の背後にある元の意味を推測することができます: 事前に指定された配列からデータ構造を構築Aし (その構築は複雑さの要件には含まれません)、後でセクションのインデックス[L1,R1],[L2,R2],...[Lt,Rt]とintegerk前に構築したデータ構造により、元の配列の複雑さkで新しく指定された index() によって定義されたセクションの中で最も高い要素を取得できます。残念ながら、私はまだこの問題の解決策を思いつきませんでした。または、そのような解決策が存在しないという証拠もありませんが、少なくとも今では問題は理にかなっています。L1,R1,L2,R2,...,Lt,RtAO(t+klogk)

どのオプションが質問の本来の意図であったかを知りたいです。オプション3の解決策を思いついた場合は、それに応じてこの回答を編集します。

于 2016-09-08T13:19:37.790 に答える
0

[0..t] をセクションによってマップされたインデックスにマップする間接テーブル T を作成します。

次に、この間接テーブルを使用して heapify アルゴリズムを実行します。アルゴリズムが A[i] にアクセスするたびに、A[T[i]] に置き換えられます。

間接テーブルの構築と heapify は両方とも O(t) です。上位 k 個の要素を取得するには、O(t log n) のコストがかかります。

編集: ウィキペディアの記事で、O(t) でヒープを構築する方法が説明されています。

基本的には、一連のバブルダウン操作です。

for i from floor(A.size()/2) to 0:
    bubble_down(A, i)

これが O(t) である理由は記事に証明されています。

于 2013-02-21T18:24:24.460 に答える