2 日前のインタビューで、配列内の最大要素を最適に見つける方法に関する質問に直面しましたが、それに関して質問があります。
インタビュアーが説明した配列は、繰り返される可能性のある整数値で構成され(連続した場所である必要はありません)、2 つの部分で構成されます (一方の部分は空である場合があります): 最初の部分は非減少順、2 番目の部分は非増加順順序、つまり、a[n] が n 個の整数値で構成される配列の場合、a[i]<=a[i+1],i in [1,m] および a[j]>=a[j+ 1],j in [m,n] であり、m は 1 と n の間のどこかにあります。今、最も効率的な方法で配列の最大値を見つけるように依頼されました。
一部の要素は繰り返される可能性があるため、分割統治戦略を使用して探索空間を要素化することはできないと主張しました。すべての要素が異なっていれば、二分探索を使用してlg n時間で最大値を見つけることができます。しかし、少なくとも 1 つの入力シーケンスが存在し (おそらくすべての要素が同じ場合)、どの要素が最大であるかを知る前に、少なくとも n-1 の比較が必要です。
インタビュアーは、問題を 1 時間以内に解決できるように、入力に何らかの制限を課すことができるかどうかを考えるように私に求めました。その時は解決できず、まだ考えていました。
考える上で参考になれば幸いです。