LeetCode 1151. 最少交换次数来组合所有的 1

2026-04-25 HGNULB 约 4 分钟

文章信息 9 个分类 2 个标签

分类

LeetCode CodeTop 中等未解决会员题 2-5 字节华为京东

题目描述

✅ 1151. 最少交换次数来组合所有的 1

题意分析

在只含 0 和 1 的线性数组中，每次可以交换任意两个位置的元素，要求用最少次数让所有 1 连续地排列在一起。

交换次数不取决于两个位置相隔多远，也不要求只能交换相邻元素。数组首尾不相连，不能把分布在两端的 1 当成一个连续区间。

解法：固定长度滑动窗口

核心思路

[!blue]

先统计数组共有多少个 1，记为 ones。交换不会改变这个数量，所以最终所有 1 一定恰好占据某个长度为 ones 的窗口，问题只剩选择这个窗口放在哪里。

对一个固定窗口，假设里面已有 windowOnes 个 1，就有 ones - windowOnes 个 0 需要换出去。窗口外恰好也有同样数量的 1，所以每个内部零都能与一个外部一交换，完成目标所需次数不超过这个数量。

另一方面，一次交换最多让窗口内增加一个 1，因此至少也需要这么多次。上下界一致，固定窗口的最优代价就是内部零的数量。

于是只要找长度为 ones、包含最多 1 的窗口，答案就是 ones - maxOnes。窗口右移一格时只新增右端、移除原左端，可以用常数次加减维护数量，不用反复扫描窗口或真的执行交换。

若总共只有零个或一个 1，已经满足要求，直接返回 0。

解题步骤

统计 ones，若不超过 1，返回 0。

从左向右扩展窗口，将新进入的元素值加到 windowOnes。

窗口超过目标长度时，减去下标 right - ones 处被移出的元素。

达到完整窗口长度后，更新历史最大的窗口一数 maxOnes。

扫描所有合法窗口，返回 ones - maxOnes。

代码实现

class Solution {
    public int minSwaps(int[] data) {
        int ones = 0;

        for (int num : data) {
            if (num == 1) {
                ones++;
            }
        }

        if (ones <= 1) {
            return 0;
        }

        int windowOnes = 0;
        int maxOnes = 0;

        for (int right = 0; right < data.length; right++) {
            windowOnes += data[right];

            // 加入右端后移出超宽的一项，维持目标长度。
            if (right >= ones) {
                windowOnes -= data[right - ones];
            }

            if (right >= ones - 1) {
                maxOnes = Math.max(maxOnes, windowOnes);
            }
        }

        // 每个窗口内的零恰好需要一次与外部一的交换。
        return ones - maxOnes;
    }
}

func minSwaps(data []int) int {
    ones := 0
    for _, num := range data {
        if num == 1 {
            ones++
        }
    }
    if ones <= 1 {
        return 0
    }

    windowOnes := 0
    maxOnes := 0
    for right := 0; right < len(data); right++ {
        windowOnes += data[right]
        // 加入右端后移出超宽的一项，维持目标长度。
        if right >= ones {
            windowOnes -= data[right-ones]
        }

        // 窗口已满时才更新窗口内 1 的最大数量，预热阶段不计入答案。
        if right >= ones-1 && windowOnes > maxOnes {
            maxOnes = windowOnes
        }
    }

    // 每个窗口内的零恰好需要一次与外部一的交换。
    return ones - maxOnes
}

复杂度分析

时间复杂度：$O(n)$，统计总数和滑动窗口各扫描一遍，每个窗口更新为常数时间。

空间复杂度：$O(1)$，只维护总数、窗口计数与最大值，不修改原数组。

关键点总结

[!green]

总一数决定了目标窗口长度，不需要枚举不同长度。

窗口内缺少的一与窗口外多出的一数量相等，每次任意交换正好补一个缺口。

最小交换数等价于最大窗口一数，滑动窗口只负责高效枚举目标位置。

易错点总结

[!yellow]

按相邻交换距离计算成本，解决的是另一种限制下的问题。

用总一数减去最长现成连续一段，只考虑了单段，忽略窗口中还能保留的其他一。

把首尾连接起来滑动，会求成环形数组版本。

返回窗口内一的最大数量，得到的是已经就位的数量；还需用总数减去它。

窗口移出下标算错，会让维护的计数不再对应恰好 ones 个位置。

相似题目

题目	难度	关联与区别
2134. 最少交换次数来组合所有的 1 II	中等	将数组改为环形后，固定长度窗口还需覆盖跨首尾的情况。
1703. 得到连续 K 个 1 的最少相邻交换次数	困难	原题只能相邻交换，代价与移动距离有关；本题任意交换，固定窗口中0的数量就是需要的交换数。

转载与许可

作者 HGNULB

链接 https://hgnulb.github.io/blog/2026/70567385

许可本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！