本文介绍一种高效计算偶数元素位移量的方法：不实际移动数组，而是通过统计每个偶数前的奇数个数，直接得出其在重排后的位置偏移量，时间复杂度 o(n)，空间最优且逻辑清晰。
本文介绍一种高效计算偶数元素位移量的方法：不实际移动数组，而是通过统计每个偶数前的奇数个数，直接得出其在重排后的位置偏移量，时间复杂度 o(n)，空间最优且逻辑清晰。
在将数组中所有偶数“移动到前端、奇数移到后端”（保持偶数间与奇数间的相对顺序不变）的问题中，一个常见误区是试图模拟真实交换过程来追踪位移——这不仅代码复杂、易出错，而且时间复杂度高达 O(n²)。实际上，每个偶数的位移量， precisely 等于它在原数组中左侧出现的奇数个数。
为什么？因为最终偶数序列紧邻排列在开头，且相对顺序不变；每个偶数只需“跳过”其前方所有奇数即可到达目标位置。例如：
int[] a = {1, 3, 2, 5, 4, 7, 8, 6};
// 索引: 0 1 2 3 4 5 6 7
// 奇偶: 奇 奇 偶 奇 偶 奇 偶 偶
// 左侧奇数个数: 2 3 4 4 → 即位移量 [2, 3, 4, 4]- 2（索引2）左侧有 1,3 → 2个奇数 → 位移量为 2
- 4（索引4）左侧有 1,3,5 → 3个奇数 → 位移量为 3
- 8（索引6）左侧有 1,3,5,7 → 4个奇数 → 位移量为 4
- 6（索引7）左侧仍有 1,3,5,7 → 4个奇数 → 位移量为 4
因此，只需一次线性遍历，维护一个累计奇数计数器 oddCount，遇到偶数即记录当前 oddCount 值，遇到奇数则递增 oddCount。
✅ 推荐实现（使用 ArrayList 动态收集）
import java.util.*;
public class EvenShiftCalculator {
public static int[] calculateEvenShifts(int[] arr) {
List<Integer> shifts = new ArrayList<>();
int oddCount = 0;
for (int num : arr) {
if (num % 2 == 0) {
shifts.add(oddCount);
} else {
oddCount++;
}
}
// 转为 int[] 数组（Java 8+）
return shifts.stream().mapToInt(Integer::intValue).toArray();
}
// 测试示例
public static void main(String[] args) {
int[] a = {1, 3, 2, 5, 4, 7, 8, 6};
int[] result = calculateEvenShifts(a);
System.out.println(Arrays.toString(result)); // 输出: [2, 3, 4, 4]
}
}⚠️ 注意事项与优化建议
- 无需修改原数组：本方法纯读取，零副作用，线程安全，符合函数式编程思想；
- 空间可控：若已知偶数个数 evenCount（如预处理统计），可直接初始化 int[] shifts = new int[evenCount] 并用索引写入，避免 ArrayList 扩容开销；
- 边界兼容：空数组、全奇数（返回空数组）、全偶数（返回全 0 数组）均自然支持；
- 扩展性强：该思路可推广至任意“稳定分区”场景（如负数前置/正数后置），位移量 = 目标区域外的干扰元素数量；
- 避免陷阱：原始代码中嵌套循环做冒泡式左移，既破坏稳定性（偶数间顺序可能错乱），又无法正确计算位移（因多次覆盖导致计数失真）。
综上，理解“位移本质是跨过干扰元素的数量”，是解决此类稳定重排位移问题的关键洞察。一次遍历、常数额外空间、语义清晰——这才是工业级代码应有的简洁与健壮。
立即学习“前端免费学习笔记（深入）”；
