algorithm - O(n) 時間で 90 パーセンタイルを計算する

Question

重複の可能性:
O(n) 償却複雑度で n 整数をソートできますか?

ソートされていない整数のリストを指定すると、「ファイル内の数値の少なくとも 90% を超える、ファイル内の最小の数値」を返すアルゴリズムを作成する必要があります。そのような数値が存在しない場合は -1 です。簡単です: マージ ソートを使用してリストをソートし、90% のインデックスから開始して、最初の数値がその前の数値よりも大きいものを探します。

ただし、質問のパート 2 で困惑しました。さらに情報が与えられます。整数は給与を表し、すべて正であり、その大部分は 1,000,000 未満です。どうやらこの追加情報を使用して、元の問題を O(n) 時間で解決するアルゴリズムを作成することが可能ですが、これがどのように可能になるかについては、まったく手がかりがありません。何か案は？

これまでに行ったことを投稿しますが、何も思いつきませんでした。

Answer 1

配列内で th 番目に大きい要素を選択する選択アルゴリズムを探しています。kウィキペディアの記事では、これを行うための O(n) アルゴリズムが提供されています。これはクイックソートに似ていますが、配列全体をソートしないため、O(n*logn) ランタイムが回避されます。

要素がすべて特定の範囲 (たとえば、この場合は 1 ～ 1000000) に制限されている場合、別の方法として、O(n) でカウント ソートまたはバケット ソートを使用してそれらをソートし、必要な要素を選択します。この場合、要素の「大部分」はすべてではなく 1000000 未満であるため、1000001 バケットでバケット ソートを実行し、1000000 を超えるすべての要素に対して最後のバケットを使用できます。