面试问题:奇偶位置上的奇偶元素(保持元素顺序)

Question

以下问题是在一次采访中提出的：

给出一个数组。任务是排列数组，以便：

• 奇数元素占据奇数位置，偶数元素占据偶数位置。

-元素的顺序必须保持不变。

• 考虑基于零的索引。
• 按条件打印后，如果剩余，则按原样打印其余元素。

示例：

输入: Arr = 2、4、6、8、10、1、3、5、7、9

产出: Arr= 2，1，4，3，6，5，8，7，10 9

是否存在无常数空间(即O(1))且在O(N)时间内的解？

Answer 1

如果有n/2偶数元素和n/2奇数元素，则解可以非常简单，保留一个“偶数指针”和“奇数指针”，指向新数组中的第一个偶数空位置，以及新数组中的第一个奇数空位置。与其简单地遍历旧数组，在正确的位置填充元素，而且不要忘记将指针增加2；如果奇数元素的数目比偶数元素差-u可以发现O(n)上有多少偶数和奇数，所以这个问题也很简单。