選択アルゴリズムが失敗する理由:
選択アルゴリズムの使用は #elements で線形であることに注意してください。#requests が #elements で線形であると仮定すると、二次解につながります。これが制限時間を超える理由です。
別のアプローチ:
最大ヒープH1と最小ヒープの 2 つのヒープを維持するH2
最大ヒープ ( H1) は 2/3 の最小値を保持し、最小ヒープは 1/3 の最大値を保持します。
次に、読み取った要素ごとにx、トップ 1/3 ヒープ ( H2) を増やす必要があるかどうかを確認します。必要な場合は、 を追加する必要がありますmax{x,H1.max()}。追加した場合H1.max()は、ヒープから削除し、x代わりに挿入する必要があります。追加が必要ない場合は、 が より大きいかどうかを確認し、x大きい場合はH2.min()最小フォームを削除してH2に挿入しH1、 に追加xしH1ます。
注: このソリューションで探している数はO(1)、いつでも見つけることができます。これは、最小ヒープ ( H2) の最小値です。
このソリューションの複雑さの合計O(nlogn + k)- ここでnは数字の数、kは「数字を伝える」リクエストの総数です。
注: より簡単な解決策 (おそらく遅くなりますが) は、並べ替えられたリストを維持し (たとえば、BSTまたはスキップリストで)、二分探索を使用して関連する要素を探すことです。
例：
init:
H1 = {}
H2 = {}
input1:
H1 = {1}
H2 = {}
input7:
H1={1,7}
H2 = {}
input 9: //need to add a max, in this case: x > H2.max() -> add x to H2.
H1 = {1,7}
H2 = {9}
tell the number
H2.min() = 9
input 21: // 21>9 -> remove H2.min() add it to H1, add x to H2
H1 = {1,7,9}
H2 = {21}
input 8:
H1 = {1,7,8,9}
H2 = {21}
input 5: //remove max from H1, add max to H2, add x to H1
H1 = {1,7,5,8}
H2 = {9,21}
tell the number
H2.min() = 9
input 11: //remove min from H2, add it to H1, add x to H2.
H1 = {1,7,5,8,9}
H2 = {11,21}
tell the number
H2.min() = 11