回転したソートされた配列に関連するいくつかの質問を見てきました。たとえば、ピボット要素の検索や、そのような配列内の要素の検索などです。
しかし、ソートを使用せずにそのような配列を元の形式に再配置することに関連する質問は見つかりませんでした。
だから私の質問：*余分なメモリを使用せずに、回転され、ソートされた配列を元の形式に再配置するための効率的な方法、またはトリックはありますか？
1 に答える
0
これが私がすることです..私は二分探索のバリエーションを使用して開始要素を見つけるでしょう。
それが見つかったら、外部メモリを使用できる場合は、O（n）で実行できます。したがって、合計時間はO（lgn）+ O（n）であり、これはO（n）です。
特にローテーションについて：ajayのコメントを見て、私たちはその場でローテーションする必要があるので、最良のオプションはバブルソートであることに同意します。これはO（n * m）です。ここで、mは回転した要素の数です。
ただし、ストレージを使用して要素を開始要素の両側に保持できる場合、基本的に、外部メモリを使用できる場合は、各要素を新しい配列の適切な場所に配置することが問題になります。
于 2012-10-23T16:36:52.053 に答える