输入一个整数数组,实现一个函数来调整该数组中数字的顺序,使得所有奇数位于数组的前半部分,所有偶数位于数组的后半部分。
解题思路:
可以仿照快速排序中 $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$ 都是常数级的额外空间。
评论区