これは面接の質問です。整数値を保持し、現在のキューの中央値要素を返すgetMedian（）関数を持つキューを設計する必要があります。O（n）の余分なスペースを使用できます。
getMedian（）は時間計算量<O（n）で実装できますか？
例：キューに次の値（2、1、2、2、6、4、2、5）がある場合、このメソッドは2を返し、そのオブジェクトを削除しません。
質問する
1084 次
1 に答える
9
問題の既知の実装は次のとおりです。
実装する必要があるのは2つのヒープで、1つは最小ヒープ、もう1つは最大ヒープになります。
また、キュー内のオブジェクトの数を示す整数が必要になります。
ヒープの制約は次のとおりです
。1。最小ヒープにはキューの大きいオブジェクトが含まれます
2.最大ヒープにはキューの小さいオブジェクトが含まれます
3.最大ヒープには同じか1つ多くなります最小ヒープよりもオブジェクト
そうすれば、オブジェクトの数が奇数の場合、中央値は正確に最大ヒープ内の最大オブジェクトになります。オブジェクトの数が偶数の場合、中央値はヒープの両方のルートの平均になります（最大ヒープの最大値、最小ヒープの最小値）。
ヒープが不均一になった場合、たとえば特定のヒープから「ポップ」する場合は、他のヒープから削除して移動する必要があることに注意することが重要です。しかし、対処する必要があるのはヒープのルートだけであり、それ以上のものではないため、これは問題ではありません。
getMedianの時間計算量はO（1）になります
ちょうど主題に関する記事を見つけました：リンク
コメントへの回答
max-heapは、最小の半分の要素を保持します。
キューに新しい番号を追加するときは、最初にキュー内のオブジェクトの数を確認します。
追加する数が偶数の場合は、両方のキューのサイズが等しいため、最大ヒープに追加する必要があることを意味します。
次に、max-heapのmaxが何であるかを確認します。
urの数よりも大きい場合は、max-heapに挿入するだけです。
小さい場合は、新しい数値が最小ヒープの数値よりも大きい可能性があることを意味します。
したがって、最小ヒープの最小値が何であるかがわかります。
数値が最小値よりも小さい場合は、最大ヒープに挿入できます。より大きい場合は、最小ヒープ内の最小値を最大ヒープに移動し、新しい数値を最小ヒープに挿入します。ヒープ。
数値が奇数の場合、最大ヒープにはもう1つあるため、最小ヒープに追加する必要があります。
それは少し複雑ですが、それでも理解できない場合は、疑似コーディングを気にしないでください
于 2012-09-18T15:01:02.033 に答える