arrays - 面试题: Even and odd elements at even and odd positions (keep elements order)

Question

面试中被问到的问题:

给定一个数组。任务是排列数组:

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

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

• 考虑从零开始的索引。
• 按条件打印后，若有剩余，则原样打印剩余元素。

例子:

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

输出:到达= 2,1,4,3,6,5,8,7,10,9

是否有没有恒定空间(即 O(1))且时间为 O(N) 的解决方案？

Answer 1

如果有 n/2 个偶数元素和 n/2 个奇数元素，解决方案可以非常简单，保留一个“偶数指针”和“奇数指针”指向新数组中第一个偶数空位置，第一个奇数空位置放置在新数组中。不仅仅是遍历旧数组，在正确的位置填充元素，并且不要忘记将指针增加 2；如果奇数元素的数量与偶数元素的数量不同 - 您可以在 O(n) 时发现偶数和奇数的数量，所以同样，问题非常简单。