解题思路
这道题我们用两个指针分别追踪奇数位和偶数位,每次检查最后一个元素是奇数还是偶数,然后把它交换到对应的位置上。
比如最后一个元素是奇数,就把它换到下一个需要填充的奇数位(1, 3, 5…),换过来的元素又成为新的"最后一个元素",继续这个过程。
这样做的优势是不需要额外空间,而且每次交换都在推进进度,最终当奇数位和偶数位都填满后,数组自然就符合要求了。
举个栗子
输入: [4, 2, 5, 7]
执行过程:
- 初始:
[4, 2, 5, 7],最后元素 7(奇数) → 交换到 odd=1 → [4, 7, 5, 2]
- 最后元素 2(偶数) → 交换到 even=0 →
[2, 7, 5, 4]
- 最后元素 4(偶数) → 交换到 even=2 →
[2, 7, 4, 5]
- 最后元素 5(奇数) → 交换到 odd=3 →
[2, 7, 4, 5]
输出: [2, 7, 4, 5]
代码实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
|
public static int[] sortArrayByParityII(int[] nums) {
int n = nums.length;
for (int odd = 1, even = 0; odd < n && even < n;) {
if ((nums[n - 1] & 1) == 1) {
// 最后一个元素是奇数,放到奇数位
swap(nums, odd, n - 1);
odd += 2;
} else {
// 最后一个元素是偶数,放到偶数位
swap(nums, even, n - 1);
even += 2;
}
}
return nums;
}
public static void swap(int[] nums, int i, int j) {
int tmp = nums[i];
nums[i] = nums[j];
nums[j] = tmp;
}
|
如果觉得有帮助，欢迎点赞、关注、转发~