数组拼图：分离偶数和奇数

Question

Segregating an array for even and odd numbers 这是重复的，但没有解决方案可以保留元素的顺序，O（n）时间和O（1）空间中是否存在这样的解决方案。

我只是觉得这是在aove

Answer 1

我怀疑它给出的重复链接中提到的方法。

您可以使用链接文章中显示的基本双指针解决方案，但不是交换奇数元素，而是可以将数组元素滑动到左侧并将奇数元素放在其位置;那就是O（n^2）时间和O（1）空间，就像插入排序一样，因为您必须访问每个元素并可能将其滑动到整个数组的整个长度。

或者您可以保留O（n）时间，但是通过对输入数组进行两次遍历，将偶数元素复制到输出数组和第二遍奇数元素，从而使用O（n）空间。

但我没有看到保存O（n）时间和O（1）空间的方法。

相反，如果你想在自己的偶数和奇数分区排序的所有元素，你可以使用标准的系统分类和比较功能是低于只有在较低索引元素一个甚至和更高索引元素b是奇数或者如果两个元素具有相同的奇偶性和a < b;在C这是(a%2==0 && b%2==1) || (a%2==b%2 && a<b)。这就是排序中堆栈的O（n log n）时间和O（log n）空间，所以它不会保留原始的时间或空间范围，也不能解决请求的问题。