第 21 题：调整数组使得奇数位于偶数之前
传送门：AcWing：调整数组顺序使奇数位于偶数前面，牛客网 online judge 地址。
输入一个整数数组，实现一个函数来调整该数组中数字的顺序。
使得所有的奇数位于数组的前半部分，所有的偶数位于数组的后半部分。
样例：
输入：
[1,2,3,4,5]输出：
[1,3,5,2,4]
分析：这道题要注意的一点就是：保持原来的顺序，具体可以参考 LeetCode 第 88 题的策略，从后向前重新为数组赋值。
思路1：有点类似“两路快排”的思路。“两路快排”中有一些细节需要复习一下。双指针扫描：用两个指针分别从首尾开始，往中间扫描。扫描时保证第一个指针前面的数都是奇数，第二个指针后面的数都是偶数。每次迭代时需要进行的操作：
1、第一个指针一直往后走，直到遇到第一个偶数为止；
2、第二个指针一直往前走，直到遇到第一个奇数为止。
交换两个指针指向的位置上的数，再进入下一层迭代，直到两个指针相遇为止。
时间复杂度：当两个指针相遇时，走过的总路程长度是 ，所以时间复杂度是
。
Python 代码：
class Solution(object):
def reOrderArray(self, array):
"""
:type array: List[int]
:rtype: void
"""
# 特判
size = len(array)
if size < 2:
return
l = 0
r = size - 1
# 始终保持 [0,l) 是奇数
# (r,size-1] 是偶数
while True:
while l <= r and array[l] & 1 == 1:
l += 1
# 此时 l 来到了第一个偶数位置
while r >= l and array[r] & 1 == 0:
r -= 1
# 此时 r 来到了第一个奇数的位置
# 这里一定是大于号，否则数组下标会越界
# 一定要特别注意，写 == 号会出错，写 >= 是可以的，因为 == 成立的时候，不用交换
if l > r:
break
array[l], array[r] = array[r], array[l]
l += 1
r -= 1
return array
C++ 代码：
image-20190108005607547
C++ 代码：
class Solution {
public:
void reOrderArray(vector<int> &array) {
int l = 0, r = array.size() - 1;
while (l <= r) {
while (array[l] % 2 == 1) l ++ ;
while (array[r] % 2 == 0) r -- ;
if (l < r) swap(array[l], array[r]);
}
}
};
思路2：把奇数数组复制出来，按照从后向前归并排序的做法完成。
Java 代码：
import java.util.Arrays;
public class Solution {
// 保证奇数和奇数，偶数和偶数之间的相对位置不变。
public void reOrderArray(int[] array) {
int len = array.length;
if (len == 0) {
return;
}
// 奇数全部挪到缓存数组中
int[] buff = new int[len];
int j = -1;
for (int i = 0; i < len; i++) {
if (array[i] % 2 == 1) {
j++;
buff[j] = array[i];
}
}
// 如果都没有奇数的话，程序终止
if (j == -1) {
return;
}
// 把偶数集中“挤”到数组的末尾
// 然后再把缓存数组中的奇数倒序放入
int k = len - 1;
for (int i = len - 1; i >= 0; i--) {
if (array[i] % 2 == 0) {
array[k] = array[i];
k--;
}
}
while (j >= 0) {
array[j] = buff[j];
j--;
}
}
public static void main(String[] args) {
int[] arr = {1, 2, 3, 4, 5};
Solution solution = new Solution();
solution.reOrderArray(arr);
System.out.println(Arrays.toString(arr));
}
}
Java 代码：
import java.util.Arrays;
public class Solution {
// 保证奇数和奇数，偶数和偶数之间的相对位置不变。
public void reOrderArray(int[] array) {
int len = array.length;
if (len == 0) {
return;
}
// 奇数全部挪到缓存数组中
int[] buff = new int[len];
int j = -1;
for (int i = 0; i < len; i++) {
if (array[i] % 2 == 1) {
j++;
buff[j] = array[i];
}
}
// 如果没有奇数，直接返回就可以了
if (j == -1) {
return;
}
// 从后向前赋值
int k = len - 1;
for (int i = len - 1; i >= 0; i--) {
if (array[i] % 2 == 0) {
array[k] = array[i];
k--;
}
}
while (j >= 0) {
array[j] = buff[j];
j--;
}
}
}
扩展：书本上有这个问题更一般的做法。
