問題タブ [quickselect]
For questions regarding programming in ECMAScript (JavaScript/JS) and its various dialects/implementations (excluding ActionScript). Note JavaScript is NOT the same as Java! Please include all relevant tags on your question; e.g., [node.js], [jquery], [json], [reactjs], [angular], [ember.js], [vue.js], [typescript], [svelte], etc.
javascript - JavaScript の numpy.partition
numpy.partitionライブラリまたは組み込みを介して、JavaScriptですぐに利用できる同等のものはありますか?
underscore.jsなどの一般的な関連ライブラリがそのような機能を提供しているようには見えません。自分でクイックセレクトやイントロセレクトnを実装することなく、一般的なケースで配列内の最高（または最低）の要素を見つけられるようにしたいので、私は尋ねています。
インデックス で配列を分割すると、 の要素がソートされた順序になり、インデックスが より大きいすべての要素が の要素よりも大きくなるように、配列が再配置されnます。または、 より小さいインデックスの要素はすべて、の要素より小さい場合があります。いずれにせよ、特定の要素の位置とその上下の要素の分布を保証するのは部分的な並べ替えです。nnnnn
完全な並べ替えはもちろん同じ条件を満たしますが、O(n log n)時間内に実行されますが、パーティショニングは通常時間内に実行されO(n)ます (quickselect の平均的なケース、introselect の最悪のケース)。
jQuery プラグインのQuickSelectは、有望な名前にもかかわらず、まったく異なることを行います。
この質問の動機の一部: Math.min を使用して配列から 2 番目に小さい数値を取得することは可能ですか?
java - QuickSelect で重複を実装する方法
配列内で k 番目に小さい数を見つけるクイック セレクト アルゴリズムを作成しました。私の問題は、重複のない配列でのみ機能することです。配列がある場合
arr = {1,2,2,3,5,5,8,2,4,8,8}
3 番目に小さい数は 2 と表示されますが、実際は 3 です。
私は何をすべきかについて行き詰まっています。ここに私の2つの方法であるquickSelectとPartitionがあります：