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. Initialize both last_odd, last_even to -1;
2. Iterate over array
- Check if array[i] is odd or even,
- if diff(last_odd/last_even,i) >= 2 and last_odd/even not equal to
-1:
if (element is odd/even) new index = last_odd/even+1
- store element value in temp
- move elements from new_index up to i one to right
starting back from i-1 down to new_index.
- store temp in new_index
- store last_odd/even as new_index accordingly and add to
last_even/odd the diff(which is +1)
- else store last_odd/even as i accordingly
关于algorithm - 奇偶分离,保序,O(1)空间,O(N)时间复杂度,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/43710667/