Input = {12, 34, 45, 9, 8, 90, 3}
Output = {12, 34, 8, 90, 45, 9, 3}
给定一个整数数组,在所有奇数之前重新排列所有偶数整数,但使用O(1)空间和O(n)时间复杂度将它们的原始序列保持在数组中 .
思想:
Algorithm: segregateEvenOdd()
1) Initialize two index variables left and right:
left = 0, right = size -1
2) Keep incrementing left index until we see an odd number.
3) Keep decrementing right index until we see an even number.
4) If lef < right then swap arr[left] and arr[right]
但这不能保证订单是一样的 .
如果我想使用O(1)空间来解决这个问题怎么办?
1 回答
你必须存储最后的奇数和最后的偶数位置,