题⽬描述
输⼊⼀个⻓度为 n 整数数组，数组⾥⾯可能含有相同的元素，实现⼀个函数来调整该数组中数字的顺序，使得所有的奇数位于数组的前⾯部分，所有的偶数位于数组的后⾯部分，对奇数和奇数，偶数和偶数之间的相对位置不做要求，但是时间复杂度和空间复杂度必须如下要求。
数据范围：0 ≤ n ≤ 50000，数组中每个数的值 0 ≤ val ≤ 10000
要求：时间复杂度 O(n)，空间复杂度 O(1)
示例 1
输⼊：[1,2,3,4]
返回值：[1,3,2,4]
说明：[3,1,2,4]或者[3,1,4,2]也是正确答案
示例 2
输⼊：[1,3,5,6,7]
返回值：[1,3,5,7,6]
说明：[3,1,5,7,6]等也是正确答案
思路及解答
这道题只需要奇数在⼀半，偶数在另外⼀半就可以，并没有要求他们之间的顺序，那么我们就可以⽤双指针，⼀个指针在左边，⼀个指针在右边，⽐如 1,3,5,6,7 :
左指针往右遍历直到找到偶数，也就是 6 停下来，
右指针往左⾛，直到找到第⼀个奇数，也就是 7 停下来。
两者交换:
左指针继续往右边⾛，两个指针相遇，结束，这个时候其实偶数已经全部在右边了。
这个例⼦⾥⾯只经过⼀次交换，如果是多次交换，那么结束的条件同样也是两个指针相遇。
public class Solution81 {
public int[] reOrderArrayTwo(int[] array) {
int low = 0;
int high = array.length - 1;
// 直到两个指针相遇
while (low < high) {
// 左指针往右查找偶数停下来
while (array[low] % 2 == 1) ++low;
// 右指针往左查找奇数停下来
while (array[high] % 2 == 0) --high;
if (low < high) {
// 交换
int temp = array[low];
array[low] = array[high];
array[high] = temp;
}
}
return array;
}
}由于只查找了⼀遍数组，那么时间复杂度为 O(n),没有借助额外的空间，所以空间复杂度为 O(1)