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).

classSolution { public: vector<int> sortArrayByParityII(vector<int>& A){ int n = A.size(); vector<int> ans(n);

int i = 0; for (int x: A) { if (x % 2 == 0) { ans[i] = x; i += 2; } } i = 1; for (int x: A) { if (x % 2 == 1) { ans[i] = x; i += 2; } } return ans; } };

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).

classSolution { public: vector<int> sortArrayByParityII(vector<int>& A){ int odd = 1; int even = 0; while(odd < A.size() && even < A.size()) { while(odd < A.size() && A[odd]%2) odd+=2; while(even < A.size() && A[even]%2 == 0) even+= 2; if(odd < A.size() && even < A.size()) swap(A[odd], A[even]); odd += 2; even += 2; } return A; } };