c++ - ソートされていない配列から上位 50 個の最大値を効率的に取得する

Question

配列に大きなデータ セット (たとえば 50000) があり、配列の上位 50 個の最大値を取得したいとします。プライオリティ キューを使用して 50 回ポップすることをお勧めしますか? 配列から優先度キューに 50000 個の要素をそれぞれ挿入すると、最大で O(n) かかる場合があり、50000 回実行すると O(n^2) になり、コストが高くなります。O の複雑さを改善するにはどうすればよいですか?

Answer 1

nth_elementを使用して、複雑さが平均 ~O(n) の上位 50 個の要素を見つけ、必要に応じて配列の 50 個の初期インデックスを並べ替えることができます。

または、要素が 50 未満であるか、現在の項目が 50 番目の要素よりも大きい限り、項目を別の priority_queue に配置して、配列を反復処理することができます。要素が 51 個あるときはいつでも、1 つポップアウトします。最悪の場合 O(n*log(50))。

最後に、配列内のすべての値が特定の制限 (<= 10^5 など) を下回っている場合は、バケット ソートを使用できます。配列全体を単純に反復処理し、++bucket[array[i]];. bucket次に、見つけた最小の 50 個の数値を書き留めて、線形に反復します。O(n) + O(m)m = 配列内の最大値である最悪のケース。