leetcode922.按奇偶排序数组II

给定一个非负整数数组A，A中一半整数是奇数，一半整数是偶数。
对数组进行排序，以便当A[i]为奇数时，i也是奇数；当A[i]为偶数时，i也是偶数。
你可以返回任何满足上述条件的数组作为答案。

示例：

输入：[4,2,5,7]
输出：[4,5,2,7]
解释：[4,7,2,5],[2,5,4,7],[2,7,4,5]也会被接受。

提示：

1. 2<=A.length<=20000
2. A.length % 2 == 0
3. 0 <= A[i] <= 1000

方法一: 两次遍历

思路和算法

遍历一遍数组把所有的偶数放进ans[0]，ans[2]，ans[4]，依次类推。

再遍历一遍数组把所有的奇数依次放进ans[1]，ans[3]，ans[5]，依次类推。

复杂度分析

• 时间复杂度：O(N)，其中N是数组A的长度。
• 空间复杂度：O(1)。注意在这里我们不考虑输出数组的空间占用。

方法二：双指针

思路与算法

如果原数组可以修改，则可以使用就地算法求解。

为数组的偶数下标部分和奇数下标部分分别维护指针i，j。随后，在每一步中，如果A[i]为奇数，则不断地向前移动j(每次移动两个单位)，直到遇到下一个偶数。此时，可以直接将A[i]与A[j]交换，我们不断进行这样的过程，最终能够将所有的整数放在正确的位置上。

复杂度分析

• 时间复杂度：O(N)，其中N是数组A的长度。
• 空间复杂度：O(1)。