数组偶数位移量：如何统计前奇数个数

本文揭示了一个巧妙而高效的算法思想：在将数组中偶数统一前移、奇数后置的重排过程中，每个偶数的实际位移量并非来自繁琐的模拟交换，而是直接等于其在原数组中左侧出现的奇数个数——这一本质洞察将问题简化为一次线性扫描，仅需O(n)时间与O(1)额外空间即可精准计算所有偶数的位移量，既避免了O(n²)的低效尝试，又天然保持偶数间的原始顺序，堪称理解数组重排类问题的“关键钥匙”。

本文介绍如何高效计算将数组中所有偶数移到前端、奇数移到后端时，每个偶数所需的位移量，核心思路是统计每个偶数前方的奇数个数，时间复杂度 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) 时间内完成（左指针填偶数，右指针填奇数），但位移计算本身无需此步骤。

综上，理解“位移 = 左侧奇数个数”这一本质洞察，是高效解决此类问题的核心。它将复杂模拟转化为简洁线性扫描，兼具正确性、可读性与性能优势。

本篇关于《数组偶数位移量：如何统计前奇数个数》的介绍就到此结束啦，但是学无止境，想要了解学习更多关于文章的相关知识，请关注golang学习网公众号！