输入一个整数数组，实现一个函数来调整该数组中数字的顺序，使得所有奇数位于数组的前半部分，所有偶数位于数组的后半部分。
解题思路：
可以仿照快速排序中 $partition$ 操作的思路，使用两个指针 $l$, $r$
-
当 $l$ 指向的是奇数时，$l$ 自增；
-
当 $r$ 指向的是偶数时，$r$ 自减；
-
$l$ 和 $r$ 指向的元素交换。
循环上面的操作，直到 $l == r$ 。
代码：
public int[] exchange(int[] nums) {
if (nums == null || nums.length == 0) {
return new int[0];
}
int l = 0, r = nums.length - 1;
while (l < r) {
while (l < r && (nums[l] & 1) == 1) {
l++;
}
while (l < r && (nums[r] & 1) == 0) {
r--;
}
swap(nums, l, r);
}
return nums;
}
private void swap(int[] nums, int i, int j) {
int tmp = nums[i];
nums[i] = nums[j];
nums[j] = tmp;
}
复杂度分析
-
时间复杂度$O(N)$：需要遍历 N 个元素。
-
空间复杂度$O(1)$：$l$ 和 $r$ 都是常数级的额外空间。