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