本文共 1193 字，大约阅读时间需要 3 分钟。

给出一个二进制数组 data，你需要通过交换位置，将数组中 任何位置 上的 1 组合到一起，并返回所有可能中所需 最少的交换次数。

示例 1：

输入：[1,0,1,0,1]输出：1解释： 有三种可能的方法可以把所有的 1 组合在一起：[1,1,1,0,0]，交换 1 次；[0,1,1,1,0]，交换 2 次；[0,0,1,1,1]，交换 1 次。所以最少的交换次数为 1。

示例 2：

输入：[0,0,0,1,0]输出：0解释： 由于数组中只有一个 1，所以不需要交换。

示例 3：

输入：[1,0,1,0,1,0,0,1,1,0,1]输出：3解释：交换 3 次，一种可行的只用 3 次交换的解决方案是 [0,0,0,0,0,1,1,1,1,1,1]。

提示：

1. 1 <= data.length <= 10^5
2. 0 <= data[i] <= 1

解题思路

一个很容易想到的思路就是先统计总共有多少个1，我们假设有m个。然后以m为滑动窗口的长度，通过滑动窗口的方式判断窗口中有多少个1（假设为n个），那么此时我们需要移动的次数就是m-n，我们只需要找最小值即可。

class Solution:    def minSwaps(self, data: List[int]) -> int:        n, m = len(data), sum(data)        cur, res = sum(data[:m]), m                for i in range(m, n):            res = min(res, m - cur)            if data[i] == 1:                cur += 1            if data[i - m] == 1:                cur -= 1        return res

当然我们也可以通过前缀和的方式统计区间内1的个数。

class Solution:    def minSwaps(self, data: List[int]) -> int:        n = len(data)        pre = [0] * (n + 1)        for i in range(1, n + 1):            pre[i] = pre[i - 1] + data[i - 1]                res = m = pre[-1]        for i in range(m, n):            res = min(res, m - (pre[i] - pre[i-m]))        return res

我将该问题的其他语言版本添加到了我的

如有问题，希望大家指出！！！

转载地址：https://coordinate.blog.csdn.net/article/details/99169544 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！