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

Question

为偶数和奇数分隔数组 这是重复的，但没有可以保留元素顺序的解决方案，在 O(n) 时间和 O(1) 空间中是否有这样的解决方案。

我可以想到在给定 aove 的重复链接中提到的方法

Answer 1

我对此表示怀疑。

您可以使用链接文章中显示的基本两指针解决方案，但您可以将数组元素向左滑动并将奇数元素放在其位置，而不是交换奇数元素；这是 O(n^2) 时间和 O(1) 空间，与插入排序相同，因为您必须访问每个元素并可能将其滑动到数组的整个长度。

或者，您可以保留 O(n) 时间，但使用 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) 空间，因此它不会保留原始的时间或空间边界，也不能解决请求的问题。