Partition an integers array into odd number first and even number second.

Example:

Given [1, 2, 3, 4], return [1, 3, 2, 4]

Solution

One simple solution is the swap method. We first find the position of the first even number in the array. Then for every odd number that follows, we swap the odd number with the position of the even number. This time complexity of this algorithm is O(n).