O（n）時間内の最大反復数とO（1）余分なスペースを確認してください

Question

O（n）時間とO（1）余分なスペースで最大反復回数

私はカウント配列を維持するソートフェーズを使うことができると思いますが、それはO（N）で実行できます。私は正しい？

しかし余分なスペースを処理する方法。他の効率的なアルゴリズムはありますか？

Answer 1

これは可能なことではありませんが、アレイの可能な数字についての詳細な知識はありません。 （c = O(1)）を使用するように準備されている一定量のメモリについては、ポイントn-1に正しい回答の可能性があり、最後の数字だけがネクタイを破るようなシーケンスがあります。この場合、定数メモリcのアルゴリズムは、1回のパスで解を見つけることができません。これは、いくつかの（一定量の）パスについても同様に機能します。

代わりにできることを見てみましょう。

• 我々が最もk固有の番号であることがわかっている場合、我々はk数字はする必要がない場合、一定のルックアップコストでカウント配列（または順不同マップを保つことによってO(k)余分なスペースとO(n)で答えを見つけることができますシーケンシャル）。しかし、k<n以外のkをバインドできない場合、これは最悪の場合にはO(n)余分なスペースになります。
• アレイをO(n log(n))にソートすると、答えはO(n)になります。したがって、合計の複雑さはO(n log(n))であり、余分なスペースはO(1)です。