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

Submission

运行时间: 65 ms

内存: 20.0 MB

class Solution:
    def minSwaps(self, data: List[int]) -> int:
        # 假设将全部的n个1聚集到i..j交换次数最少
        # 则i和j要满足j - i + 1 == n
        # 而且data[i..j]中原有的1的数量最多
        n = data.count(1)
        # 维护一个长度为n的滑动窗口, 并记录窗口内1的数量cnt
        # 并记录cnt的最大值
        max_ = cnt = sum(data[:n])
        
        for a, b in zip(data, data[n:]):
            cnt += b - a
            if cnt > max_: max_ = cnt
        
        return n - max_

Explain

该题目要求将所有的1聚集到数组中的某个连续子区间中，并求出需要的最少交换次数。解题思路是使用滑动窗口。首先计算数组中1的总数n，然后维持一个长度为n的滑动窗口，通过遍历数组来确定在哪个位置的窗口内1的数量最多。由于窗口长度固定为n，窗口内最多的1意味着该区间内需要交换的0最少，因此总的交换次数就是n减去窗口内1的最大数量。

时间复杂度: O(n)

空间复杂度: O(1)

class Solution:
    def minSwaps(self, data: List[int]) -> int:
        # 计算数组中1的总数
        n = data.count(1)
        # 初始化窗口内1的数量
        max_ = cnt = sum(data[:n])
        # 使用滑动窗口遍历数组，更新窗口内1的最大数量
        for a, b in zip(data, data[n:]):
            cnt += b - a
            if cnt > max_: max_ = cnt
        # 计算最小交换次数：总1的数量减去窗口内最大1的数量
        return n - max_

Explore

滑动窗口方法在解决这个问题时具有高效的时间复杂度和简洁的逻辑优势。通过固定窗口大小为1的总数n，可以直接关注于如何通过最小化交换次数将所有1聚集在此窗口内。这种方法避免了复杂的重排操作或多次遍历数组，只需单次遍历即可得出结果。相比于可能的其他方法，如直接计算每个位置到1的距离并排序这些距离进行交换，滑动窗口方法在时间和空间上都更加高效。

如果数组长度小于1的总数n，实际上这种情况在问题设定中是非法的，因为无法形成一个长度为n的窗口。在实际应用中应该首先检查这一点，如果发生这种情况，应返回错误或特定的输出，表示输入数据不合理。在编写代码时，可以增加一个条件检查来确保数组长度不小于n。

这行代码用于在数组中移动滑动窗口，并更新窗口内1的数量。`for a, b in zip(data, data[n:])`迭代遍历从数组开始至数组长度减去n的每个元素（a），同时从数组的第n个元素开始至数组末尾的每个元素（b）。在每次迭代中，元素a从窗口移出，元素b进入窗口。窗口内1的数量更新为`cnt += b - a`，即从当前1的数量中减去移出的元素a的值，并加上新进入的元素b的值。这种方式能够高效地更新每个新窗口状态，无需每次重新计算窗口内的1的数量。

在这个算法实现中，通过`zip(data, data[n:])`自然地保证了窗口始终为长度n，因为它将数组的前半部与偏移n位置的后半部进行配对，确保每次迭代中的滑动窗口都恰好包含n个元素。一旦迭代完成，就意味着窗口从数组的开始滑动到了末尾，而且每次都是长度为n。这种机制简化了窗口大小管理，避免了在数组末尾时窗口缩小的情况。