Segregated even and odd numbers, save order, O (1) space, O (N) time complexity
Input = {12, 34, 45, 9, 8, 90, 3}
Output = {12, 34, 8, 90, 45, 9, 3}
Given an integer array, swap all even integer in front of all odd numbers, but keep their original sequence in the array using O (1) space and O (n) time complexity.
think:
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]
But this cannot guarantee that the order is the same.
What if I want to use O (1) space to solve this problem?
+3
source to share
1 answer
You need to store the last odd and last even position,
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
-1
source to share