将0或1移到列表一侧的最小相邻交换次数Java代码问题求解

代码问题排查 #

• 交换判断逻辑错误：自定义的两个判断条件仅能匹配极少数相邻交换场景，无法覆盖所有需要交换的情况，同时没有按照题目要求计算「0移左、0移右、1移左、1移右」四种方案的最小值，仅执行了单一的未知移动逻辑，自然结果不符合预期
• 实现方式冗余：不需要真实模拟相邻交换过程，可通过数学方法直接计算交换次数，你当前模拟交换+每次新建ArrayList的写法不仅效率低，还容易出现数组操作的边界错误
• 边界覆盖不全：for循环的遍历范围是i < arr.size() - 1，会漏掉数组末尾两个元素的交换判定

正确实现思路 #

题目要求选择将所有0/所有1移动到列表任意一端的最小交换次数，我们只需要分别计算四种可行方案的交换次数，取最小值即可：

计算交换次数的核心逻辑：相邻交换的总次数等于需要移动的元素跨过的其他元素的总数量，无需真实模拟交换操作。

以计算所有0移动到右端的交换次数为例：

1. 先统计数组中0的总个数count0
2. 每个0最终的位置从右往左依次是 n-1, n-2, ..., n-count0
3. 遍历数组收集所有0的原始下标，第k个0（从0开始计数）的交换次数为 (n - count0 + k) - 原始下标
4. 所有0的交换次数累加，就是该方案的总交换次数
   同理可快速计算另外三种方案的交换次数。

正确Java实现代码 #

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class MinSwapBinary {
    public static void main(String[] args) {
        List<Integer> arr = Arrays.asList(1, 1, 1, 1, 0, 1, 0, 1);
        System.out.println(getMinSwap(arr)); // 输出3，符合示例预期
    }

    private static int getMinSwap(List<Integer> arr) {
        int n = arr.size();
        List<Integer> zeroIndex = new ArrayList<>();
        List<Integer> oneIndex = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            if (arr.get(i) == 0) zeroIndex.add(i);
            else oneIndex.add(i);
        }
        int count0 = zeroIndex.size();
        int count1 = oneIndex.size();

        int zeroToLeft = 0, zeroToRight = 0, oneToLeft = 0, oneToRight = 0;
        for (int k = 0; k < count0; k++) {
            zeroToLeft += zeroIndex.get(k) - k;
            zeroToRight += (n - count0 + k) - zeroIndex.get(k);
        }
        for (int k = 0; k < count1; k++) {
            oneToLeft += oneIndex.get(k) - k;
            oneToRight += (n - count1 + k) - oneIndex.get(k);
        }

        return Math.min(Math.min(zeroToLeft, zeroToRight), Math.min(oneToLeft, oneToRight));
    }
}

内容的提问来源于stack exchange，提问作者krishna thota