配列を与えられたすべての要素に対して、与えられた要素の右側にある現在の要素よりも小さい最小の要素を見つける必要があります。配列内の次の大きい要素を見つける
数学的には、配列A内のすべてのインデックスiについては 、私は強引なソリューションをO(n^2)になり、すべてのインデックスi
ためjを見つける必要があるjな
A[j] > A[i]
j > i
A[j] - A[i] is minimum
というインデックスを見つける必要があります私はより良いことを望んでいます。私はO(n log n)解決策は、自己バランスBSTを使用して可能ですが、それはかなり複雑なようだと思っています。さらに、O(n)ソリューションが必要です。
O(n)この問題に対する解決策はありますか？下限がO(n log n)であるという証拠はありますか？ O（nlogn）の
証明下限：（比較ベースのアルゴリズムについては）
我々はO（n）の中で、このタスクを達成するでしょう比較ベースのアルゴリズムを考えてみましょう。それは各指標のために、私たちは右に直接大きな要素を持っています（R [i]）。
同様に、このアルゴリズムを逆入力配列で実行し、その結果を逆にすることができます。各インデックスについて、左に直接的に大きな要素（L [i]）があります。
これは、各要素について、配列= min（R [i]、L [i]）のすぐ上の大きい要素を持つことを意味します。
この情報を使用して配列を並べ替えることができるようになりました。
配列内の最小要素を検索します。その後継者（すぐ上の大きな要素）、その後継者の後継者などを探します。したがって、配列全体がソートされた順序で取得されます。
O（n）の配列を比較のみを使用してソートしました（矛盾）。
O（nlogn）アルゴリズム：
スタートアレイの右からバランスBSTを構築します。ノードには、値とそれぞれのインデックスが含まれます。
新しい要素が見つかるたびに、それをBSTに挿入すると、対応する最も近いより大きなインデックス/値が得られます。
正確に記述した方法に基づいて完全にソートすることはできません。私たちは、全体的なものではなく、その右側に大きな要素を持っています。あなたは明確にしていただけますか？ –
@AkashdeepSaluja私たちは、その右に直接大きな要素（R [i]）を見つけます。同様に、このアルゴリズムを逆に実行することにより、左に直接的に大きな要素（L [i]）を見つけることができます。これは、直ちにより大きな要素= min（R [i]、L [i]）を有することを意味する。 –
元の配列に値とインデックスを含む型を作成し、値をソートすることで 'O（n log n）'アルゴリズムを得ることもできます。 – Codor
インデックスごとに検索する必要がありますか？または特定のインデックスのみ？ –
入力が「A」と「i」の場合、目的の出力は 'j'、s.tです。述べられた条件は成り立つか？ – Nicolas
私はすべてのインデックスに必要です。入力は '' A''です。出力はすべてのインデックス '' i''に '' j''を含む配列 '' B''です –