本文介绍如何高效计算将数组中所有偶数移到前端、奇数移到后端时，每个偶数所需的位移量，核心思路是统计每个偶数前方的奇数个数，时间复杂度 o(n)，无需实际移动元素。
本文介绍如何高效计算将数组中所有偶数移到前端、奇数移到后端时，每个偶数所需的位移量，核心思路是统计每个偶数前方的奇数个数，时间复杂度 o(n)，无需实际移动元素。
在解决“按奇偶重排数组并记录偶数位移”问题时，一个常见误区是试图模拟真实交换过程（如冒泡式左移），这不仅效率低（O(n²)），还容易混淆位移逻辑。实际上，每个偶数的位移量，严格等于它在原数组中左侧出现的奇数个数——因为所有偶数保持相对顺序，仅需“跨过”前方的奇数即可抵达最终位置。
例如，对数组 int[] a = {1, 3, 2, 5, 4, 7, 8, 6}：
- 索引 0 的 1（奇）→ 不记录；
- 索引 1 的 3（奇）→ 不记录，但累计奇数计数为 2；
- 索引 2 的 2（偶）→ 前方有 2 个奇数（1 和 3），位移量为 2；
- 索引 3 的 5（奇）→ 计数增至 3；
- 索引 4 的 4（偶）→ 前方有 3 个奇数（1、3、5），位移量为 3；
- 后续 8 和 6 分别对应前方奇数个数 4 和 4（因 7 是第 4 个奇数）；
最终位移数组为 {2, 3, 4, 4}，与预期完全一致。
✅ 推荐实现（O(n) 时间，O(1) 额外空间，不含 List）：
public static int[] calculateEvenShifts(int[] arr) {
// 第一次遍历：统计偶数个数，确定结果数组长度
int evenCount = 0;
for (int x : arr) {
if (x % 2 == 0) evenCount++;
}
// 初始化结果数组
int[] shifts = new int[evenCount];
// 第二次遍历：边计数边填充
int oddSoFar = 0;
int shiftIndex = 0;
for (int x : arr) {
if (x % 2 == 0) {
shifts[shiftIndex++] = oddSoFar;
} else {
oddSoFar++;
}
}
return shifts;
}
? 关键注意事项：
- ✅ 位移定义明确：此处“位移量”指该偶数在重排后所处索引减去其原始索引（即向左移动的步数），等价于其左侧奇数总数；
- ❌ 不依赖实际重排：无需修改原数组或执行任何交换，避免冗余操作和边界错误；
- ⚠️ 相对顺序保障：该方法天然维持偶数间的原始相对顺序（如 2 在 4 前，则结果中 2 仍在 4 前），符合题目隐含要求；
- ? 若需同时返回重排后的数组，可基于相同逻辑用双指针法在 O(n) 时间内完成（左指针填偶数，右指针填奇数），但位移计算本身无需此步骤。
综上，理解“位移 = 左侧奇数个数”这一本质洞察，是高效解决此类问题的核心。它将复杂模拟转化为简洁线性扫描，兼具正确性、可读性与性能优势。
