algorithm - 奇偶分离，保序，O(1)空间，O(N)时间复杂度

Question

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)的空间来解决这个问题呢？

Answer 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