それで、私は K の最良の候補の問題の奇妙な逆を求められました。通常の問題は次のとおりです。
以下のようなタイムスタンプと候補のタプルである「投票」のリストが与えられた場合:
(111111, Clinton)
(111111, Bush)
...
最多得票数の上位 K 候補を返します。
これは典型的な問題であり、解決策は候補のハッシュマップを使用することです-> タイムスタンプ バウンド内の投票は、サイズ K の最小ヒープも構築します。基本的にヒープの上部は、K の最良の候補から排出されやすい候補です。 .
最後に、ヒープを返します。
しかし、最後に尋ねられました: K 個の候補のリストが与えられた場合、これらに一致するタイムスタンプを K 個の最良の候補として返します。質問を 100% 正しく思い出せるかどうかはわかりません。なぜなら、これらの K 人の候補者が最高として最初に出現するか、彼らの投票集計が与えられたからです。