Given an array A of non-negative integers, half of the integers in A are odd, and half of the integers are even.
Sort the array so that whenever A[i] is odd, i is odd; and whenever A[i] is even, i is even.
You may return any answer array that satisfies this condition.
Iterate the array twice
One obvious solution is iterating the array, put odd and even values into suitable positions. Because we don’t care the order of elements.
Time complexity O(N), space complexity is O(N).
Swap even and odd positions
Another solution is try to find a pair of indexes which is not follow the required property, then swap them.
We continue to do this until we go through the whole array.
Time complexity is O(N).
Preparing for an interview? Check out this!