配列を与えられたすべての要素に対して、与えられた要素の右側にある現在の要素よりも小さい最小の要素を見つける必要があります。配列内の次の大きい要素を見つける
数学的には、配列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)の
インデックスごとに検索する必要がありますか?または特定のインデックスのみ? –
入力が「A」と「i」の場合、目的の出力は 'j'、s.tです。述べられた条件は成り立つか? – Nicolas
私はすべてのインデックスに必要です。入力は '' A''です。出力はすべてのインデックス '' i''に '' j''を含む配列 '' B''です –