数値の配列があり、この配列は不規則であり、少なくとも n 個の数値がそれよりも大きい最大数 (n) を見つける必要があります (この数値は配列にある場合と配列にない場合があります)
たとえば、2 5 7 6 9 を与えると、数値 4 は、少なくとも 4 つの数値 (またはそれ以上) が 4 よりも大きい (5 6 7 9 の方が大きい) 最大数です。
私はこの問題を解決しますが、それは数字の大きな配列に時間制限を与えると思うので、別の方法でこの問題を解決したいので、ソートにマージソートを使用します.nlog（n） が必要で、カウンターを使用してカウントします1 から k まで k よりも多い数の k がある場合は、もう一度数えます。
それは良いですか、それとも時間制限を与えますか？誰か別のアイデアがありますか？
ありがとう
c++呼び出される関数があり、std::nth_element線形時間で配列の n 番目の要素を見つけることができます。この関数を使用すると、N - n- 番目の要素 (Nは配列内の要素の総数) を見つけて、そこから 1 を引く必要があります。
で解決策を探すときC、この機能を利用することはできませんが、同様に解決策を実装できます。nth_elementqsort と非常によく似た処理を実行しますが、n 番目の要素がある配列の部分でのみ分割を実行します。
nth_elementここで、実装したとしましょう。二分探索と を組み合わせたようなものを実行しますnth_element。まず、質問の答えが配列の中央の要素 (つまり、N/2 番目の要素) であると仮定します。を使用してth 要素nth_elementを見つけます。N/2それが私たちが知っているよりも多い場合N/2、あなたの問題に対する答えは少なくともN/2です。それ以外の場合は、それより少なくなります。いずれにせよ、答えを見つけるために、N/2th 要素によって作成された 2 つのパーティションのうちの 1 つだけを続行します。このパーティションが正しいもの (要素がよりも大きいN/2) である場合、同じ問題を解決し続けます。MN/2xx + N/2 > M. 2 つの部分問題の複雑さは同じです。関心のある間隔が length になるまで、この操作を続けます1。
上記のアルゴリズムの複雑さが線形であることを証明しましょう。1つ目nth_elementは の順序で線形に操作を実行しN、2つ目nth_elementは配列の半分のみを考慮しN/2て 3 つ目の順序で操作を実行します - の順序などN/4です。全体として、 の順序で操作を実行しますN + N/2 + N/4 + ... + 1。この合計はそれよりも小さい2 * Nため、複雑さは依然として線形です。
あなたのソリューションは、複雑さがあるため、上記で提案したものよりも漸近的に遅くなりますが、O(n*log(n))私のソリューションの複雑さはO(n)です。
ピボット値を使用するソート アルゴリズムの修正版を使用します。
その理由は、ソートする要素をできるだけ少なくしたいからです。
したがってqsort、基本アルゴリズムとして使用し、ピボット要素でソートするパーティションを制御します (ソートする必要があるのは 1 つだけです)。