Given an array of integers nums, half of the integers in nums are odd, and the other half are even.

Sort the array so that whenever nums[i] is odd, i is odd, and whenever nums[i] is even, i is even.

Return any answer array that satisfies this condition.

&nbsp;
Example 1:

Input: nums = [4,2,5,7]
Output: [4,5,2,7]
Explanation: [4,7,2,5], [2,5,4,7], [2,7,4,5] would also have been accepted.


Example 2:

Input: nums = [2,3]
Output: [2,3]


&nbsp;
Constraints:


	2 &lt;= nums.length &lt;= 2 * 104
	nums.length is even.
	Half of the integers in nums are even.
	0 &lt;= nums[i] &lt;= 1000


&nbsp;
Follow Up: Could you solve it in-place?

class Solution:
    def sortArrayByParityII(self, nums: List[int]) -> List[int]:
        arr = [None]*len(nums)
        even,odd = 0,1
        for i in(nums):
            if i % 2 == 0:
                arr[even] = i
                even +=2
        for i in (nums):
            if i % 2 != 0:
                arr[odd] = i
                odd+=2
        return arr
class Solution {
    public int[] sortArrayByParityII(int[] nums) {
        
        int[] ans = new int[nums.length];
        
        int even_pointer = 0;
        int odd_pointer = 1;
        
        for(int i = 0; i < nums.length; i++){
            
            if(nums[i] % 2 == 0){
                ans[even_pointer] = nums[i];
                even_pointer += 2;
            } else{
                ans[odd_pointer] = nums[i];
                odd_pointer += 2;
            }
            
        }
        
        return ans;
    }
}
class Solution {
public:
    vector<int> sortArrayByParityII(vector<int>& nums) {

        vector<int>ans(nums.size());

        int even_idx=0;
        int odd_idx=1;

        for(int i=0;i<nums.size();i++)
        {
            if((nums[i]%2)==0) //the num is even
            {
                ans[even_idx]=nums[i];
                even_idx+=2;
            }
            else //the num is odd
            {
                ans[odd_idx]=nums[i];
                odd_idx+=2;
            }
        }
        return ans;
    }
};
var sortArrayByParityII = function(nums) {
    let arrEven = []
    let arrOdd = []
    let result = []
    for(let i in nums){
    nums[i]%2==0 ? arrEven.push(nums[i]) : arrOdd.push(nums[i])
    }
    for(let i in  arrEven){
        result.push(arrEven[i])
        result.push(arrOdd[i])
    }
   return result
};
Sort Array By Parity II