What is the key insight in Minimum Swaps to Group All 1's Together II?

The number of 1's in the array defines a fixed window size, and the minimum swaps equal the fewest zeros within any window, accounting for circular wrapping.

Can this problem be solved without a sliding window?

A brute-force approach exists but is inefficient; the sliding window with running zero counts provides O(n) time solution, which is optimal.

How do I handle the circular property in implementation?

Duplicate the array or use modulo arithmetic to slide the window across the end and start seamlessly, ensuring all circular positions are checked.

What is the time and space complexity of the sliding window method?

Time complexity is O(n) because the array is traversed once, and space complexity is O(1) since only counters and indices are stored.

What common mistakes should I avoid in this problem?

Avoid miscounting zeros in windows, ignoring the circular wrap, and incorrectly adjusting the window size instead of using the total count of 1's.

#2134

Medium

auto_awesome滑动窗口（状态滚动更新）

LeetCode 题解工作台

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

交换定义为选中一个数组中的两个互不相同的位置并交换二者的值。环形数组是一个数组，可以认为第一个元素和最后一个元素相邻。给你一个二进制环形数组 nums ，返回在任意位置将数组中的所有 1 聚集在一起需要的最少交换次数。示例 1：输入： nums = [0,1,0,…

数组滑动窗口

题目描述

交换定义为选中一个数组中的两个 互不相同 的位置并交换二者的值。

环形数组是一个数组，可以认为 第一个 元素和 最后一个 元素相邻。

给你一个 二进制环形 数组 nums ，返回在 任意位置 将数组中的所有 1 聚集在一起需要的最少交换次数。

示例 1：

输入：nums = [0,1,0,1,1,0,0]
输出：1
解释：这里列出一些能够将所有 1 聚集在一起的方案：
[0,0,1,1,1,0,0] 交换 1 次。
[0,1,1,1,0,0,0] 交换 1 次。
[1,1,0,0,0,0,1] 交换 2 次（利用数组的环形特性）。
无法在交换 0 次的情况下将数组中的所有 1 聚集在一起。
因此，需要的最少交换次数为 1 。

示例 2：

输入：nums = [0,1,1,1,0,0,1,1,0]
输出：2
解释：这里列出一些能够将所有 1 聚集在一起的方案：
[1,1,1,0,0,0,0,1,1] 交换 2 次（利用数组的环形特性）。
[1,1,1,1,1,0,0,0,0] 交换 2 次。
无法在交换 0 次或 1 次的情况下将数组中的所有 1 聚集在一起。
因此，需要的最少交换次数为 2 。

示例 3：

输入：nums = [1,1,0,0,1]
输出：0
解释：得益于数组的环形特性，所有的 1 已经聚集在一起。
因此，需要的最少交换次数为 0 。

提示：

1 <= nums.length <= 10⁵
nums[i] 为 0 或者 1

lightbulb

解题思路

方法一：滑动窗口

我们先统计数组中 $1$ 的个数，记为 $k$ ，那么题目实际上就是求一个长度为 $k$ 的环形子数组，使得子数组中 $1$ 的个数最多，那么最少交换次数就是 $k$ 减去子数组中 $1$ 的个数最多的那个子数组中 $1$ 的个数。

我们可以使用滑动窗口来解决这个问题，首先统计数组中前 $k$ 个元素中 $1$ 的个数，记为 $cnt$ ，然后我们维护一个长度为 $k$ 的滑动窗口，每次向右移动一个位置，更新 $cnt$ ，同时更新最大的 $cnt$ 值，即 $mx = \max(mx, cnt)$ ，最后答案就是 $k - mx$ 。

时间复杂度 $O(n)$ ，其中 $n$ 是数组 $nums$ 的长度。空间复杂度 $O(1)$ 。

1

2

3

4

5

6

7

8

9

10

11

class Solution:
    def minSwaps(self, nums: List[int]) -> int:
        k = nums.count(1)
        mx = cnt = sum(nums[:k])
        n = len(nums)
        for i in range(k, n + k):
            cnt += nums[i % n]
            cnt -= nums[(i - k + n) % n]
            mx = max(mx, cnt)
        return k - mx

speed

复杂度分析

指标	值
时间	complexity is O(n) because the array is traversed once with the sliding window. Space complexity is O(1) since only counters and window indices are maintained.
空间	O(1)

psychology

面试官常问的追问

外企场景

question_mark
Mentions circular array handling and sliding window optimization.
question_mark
Focuses on fixed window size based on total 1's.
question_mark
Checks understanding of running count updates to minimize swaps.

warning

常见陷阱

外企场景

error
Forgetting to account for the circular nature of the array when sliding the window.
error
Using a dynamic window size instead of the fixed number of 1's, leading to incorrect swaps count.
error
Miscounting swaps by not counting zeros in the current window correctly.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Minimum swaps to group all 0's together in a circular array using the same sliding window approach.
arrow_right_alt
Non-circular version where the array ends are not adjacent.
arrow_right_alt
Find maximum 1's in a subarray of fixed length to determine potential swaps in a circular array.

help

常见问题

外企场景

继续练习

#2106 摘水果 #2090 半径为 k 的子数组平均值 #2009 使数组连续的最少操作数