マルチセットを介して O(n) の k 番目の要素を検索することは可能ですか (値は繰り返すことができます)?
クイック選択のアイデアを理解している限り、ピボットを使用して入力を分割する必要があるためです。次に、再帰検索用に選択する2つの配列があります。これは、検索しているインデックス要素と、たとえば両方の配列のサイズによって異なります。
1 7 8 5 3 2 4
ピボットが 4 だとしましょう。私は 2 番目に大きな要素を探しています。したがって、パーティショニング後、次のような順序になる可能性があります
1 3 2 4 7 8 5
右側のサブ配列は 3 つの要素で構成されているため、正しい場合は右側の配列で 2 番目に大きいものを見つけようとしますか?
しかし、ピボットとして 8 を使用すると、次のような結果が得られる可能性があります。
1 3 2 7 5 4 8
したがって、左のテーブル内で最大の要素を見つけようとします（おそらく線形ですが、一般的には左のサブ配列を取得して要素を検索します-（|右のサブ配列サイズ| + 1））
しかし、マルチセットはどうですか? 私が配列を持っているとしましょう：
4 5 6 7 7 7 4 3 2 1
そして、私のピボットは 6 番目に大きい要素を検索することです。
4 5 3 2 4 1 6 7 7 7
したがって、上記のアプローチを使用すると、右側のサブ配列で再帰を実行しようとしますが、3 番目に大きい値は左側にある 5 であることが明らかですか?
私が思いついた唯一の解決策は、BST、Setなどのデータ構造を使用して、O(nlogn)で繰り返しを除外することです。次に、O(n) クイック選択を使用します。しかし、全体としては非線形のアプローチになりましたが、これを線形にすることはできますか?
追加の質問もありますが、メモリの割り当てができない場合はどうすればよいですか? そして、私ができることは、ローカル ints + スタック再帰のみを使用することです。問題は O(n) で解決できますか? O(nlogn) は、並べ替え + 線形の「カウントを通過する」ことで実行できるためです。