配列パズル：偶数と奇数を分離する

Question

Segregating an array for even and odd numbers これは重複していますが、要素の順序を保持できる解決策はありません。O（n）時間とO（1）領域にはそのような解決策があります。

私はちょうど私がそれを疑う

Answer 1

aove与えられた重複リンクに記載されているアプローチと考えることができます。

リンクされた記事に示されている基本的な2ポインターのソリューションを使用できますが、奇数要素に置き換える代わりに、配列要素を左にスライドさせて奇数要素をその場所に置くことができます。それはO（n^2）時間とO（1）空間です。これは、各要素を訪問し、配列全体の長さをスライドさせる必要があるため、挿入ソートと同じ方法です。

または、入力配列を2回通過させて、最初のパスで出力配列に、偶数要素を2番目のパスで奇数要素にコピーすることで、O（n）時間を保存できます。

しかし、O（n）時間とO（1）の両方の領域を保存する方法はありません。あなたが彼らの偶数と奇数のパーティションにソートされたすべての要素が必要な代わりにする場合は、標準システムのソートとのみ低インデックス付き要素が偶数で、より高い場合は小なりある比較関数を使用することができ

-indexed要素bが奇数であるか、または両方の要素が同じパリティを持つ場合、a < b; Cのそれは(a%2==0 && b%2==1) || (a%2==b%2 && a<b)です。これは、ソートのスタックのO（n log n）時間とO（log n）スペースなので、元の時間またはスペースの境界は保持されず、要求された問題も解決されません。