面试中被问到的问题:
给定一个数组。任务是排列数组:
- 奇数元素占据奇数位置,偶数元素占据偶数位置。
- 元素的顺序必须保持不变。
- 考虑从零开始的索引。
- 按条件打印后,若有剩余,则原样打印剩余元素。
例子:
输入: 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) 的解决方案?
最佳答案
如果有 n/2 个偶数元素和 n/2 个奇数元素,解决方案可以非常简单,保留一个“偶数指针”和“奇数指针”指向新数组中第一个偶数空位置,第一个奇数空位置放置在新数组中。不仅仅是遍历旧数组,在正确的位置填充元素,并且不要忘记将指针增加 2; 如果奇数元素的数量与偶数元素的数量不同 - 您可以在 O(n) 时发现偶数和奇数的数量,所以同样,问题非常简单。
关于arrays - 面试题: Even and odd elements at even and odd positions (keep elements order),我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/57064175/