偶数と奇数の配列の分離 これは複製ですが、要素の順序を保持できる解決策はありません.O(n)時間とO(1)空間にそのような解決策はありますか.
上記の重複リンクに記載されているアプローチを考えることができます
1 に答える
0
疑わしい。
リンク先の記事に示されている基本的な2ポインターソリューションを使用できますが、奇数要素を交換する代わりに、配列要素を左にスライドさせて、その場所に奇数要素を配置することができます。これは、挿入ソートと同じようにO（n ^ 2）時間とO（1）スペースです。これは、各要素にアクセスして、配列の全長にわたってスライドさせる必要があるためです。
または、O（n）時間を保持し、入力配列を2回通過させ、最初のパスで偶数要素を出力配列にコピーし、2番目のパスで奇数要素をコピーすることでO（n）スペースを使用することもできます。
しかし、O（n）時間とO（1）スペースの両方を保持する方法がわかりません。
代わりに、すべての要素を偶数と奇数のパーティションで並べ替える場合は、標準のシステム並べ替えと、インデックスの低い要素aが偶数で、インデックスの高い要素bが奇数の場合よりも少ない比較関数を使用できます。または、両方の要素のパリティが同じで、a < bの場合。Cではそれは(a%2==0 && b%2==1) || (a%2==b%2 && a<b)です。これは、ソート内のスタックのO（n log n）時間とO（log n）スペースであるため、元の時間またはスペースの境界を保持せず、要求された問題も解決しません。
于 2012-04-23T21:19:40.760 に答える