ある質問にインタビューされたばかりですが、答えはどうあるべきか知りたいです。問題は、本質的に次のとおりでした。
n個の整数のソートされていないリストがあるとします。このリストでk個の最小値をどのように見つけますか？つまり、[10、11、24、12、13]のリストがあり、2つの最小値を探している場合は、[10、11]が得られます。
私はO（n * log（k））ソリューションを持っており、それが私の最善ですが、他の人が何を思いついているのか興味があります。私は自分の解決策を投稿することで人々の脳を汚染することを控え、しばらくしてそれを編集します。
編集＃1：たとえば、次のような関数：list getMinVals（list＆l、int k）
編集＃2：それは選択アルゴリズムのように見えるので、私も自分のソリューションを投入します。リストを反復処理し、優先キューを使用して最小値を保存します。優先度付きキューの仕様では、最大値が優先度付きキューの一番上になるため、一番上を要素と比較すると、一番上がポップされ、小さい方の要素がプッシュされます。これは、優先キューにO（log n）プッシュとO（1）ポップがあることを前提としています。