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

环形数组上，这道题要凑出什么

给一个只含 0 和 1 的环形数组 nums，环形是说第一个和最后一个元素也算挨着。一次交换任选两个位置互换它们的值，问最少换几次能把所有的 1 挪到相邻的一段里。题面 nums=[0,1,0,1,1,0,0]，三个 1 分散在位置 1、3、4，只要一次交换换成 [0,1,1,1,0,0,0] 就全挨上了，答案是 1。

把 1 往哪段凑，为什么不能每种摆法都数一遍

所有 1 最终要占一段连续格子，那段落在哪、要挑。若把每个可能的落点都摆一遍、每摆一次就重新数这段里已经有几个 1、还缺几个得换进来，一段长度是 1 的个数、落点有 n 种，每种从头数一遍，就是 O(n²)，数组一长就吃力。

为什么那段的长度，铁定等于 1 的总数

先把 1 的总数记成 k。不管最后 1 聚在哪，聚拢后正好是 k 个 1 挨成一排，占据的就是长度恰为 k 的一段——多一格少一格都装不下正好 k 个 1。于是落点虽多，每个都对应一个长度 k 的窗口。窗口里本来就是 1 的留着不动，每一个 0 都得花一次交换、把窗外的某个 1 换进来。所以这个窗口要的交换次数，正好等于窗口里 0 的个数。窗口里 1 越多，0 越少，越省。要找的就是 1 最多的那个窗口，答案 = k 减窗口内最多的 1。

窗口怎么在环上滑一圈，又不用每步重数

把长度 k 的窗口先停在最左，框住前 k 格，数出里面有几个 1 记作 cnt，也把见过的最大值 mx 记成它。之后窗口每次整体右移一格：右端进来一格就把它的值加到 cnt，左端出去一格就把它的值从 cnt 减掉，一进一出只做两次常数操作，不必重数。下标一旦超过末尾就取模绕回开头，这样横跨首尾的窗口也覆盖得到——最优的一段 1 可能正跨在数组末尾和开头之间。滑满一圈、每个起点都试过，mx 就是全局最多的 1。

顺着 [0,1,0,1,1,0,0] 把每个窗口的账结一遍

先数出 3 个 1，起手窗口 [0,1,2] 是 0、1、0，cnt=1，mx=1。右移到 [1,2,3]，进位置 3 的 1、出位置 0 的 0，cnt=2，mx 刷到 2。再到 [2,3,4]，进 1 出 1，cnt=2。[3,4,5] 进 0 出 0，cnt=2。[4,5,6] 进 0、出位置 3 的 1，cnt=1。[5,6,0] 右端取模绕回开头，进 0 出 1，cnt=0。[6,0,1] 进 1 出 0，cnt=1。[0,1,2] 回到起点，cnt=1。滑满一圈 mx=2，答案 k 减 mx = 3 减 2 = 1。

窗口长度取错、忘了绕圈，答案会往哪偏

数一遍 1 是 O(n)，滑一圈 n 步每步常数，整体 O(n)；只用 k、cnt、mx 几个整数变量，空间 O(1)。几处一写就偏：窗口长度必须恰好是 k，随手换个别的值，对应的就不是一个装得下 k 个 1 的合法目标段。只在直线上滑、不给下标取模，横跨末尾和开头的那些窗口会被漏掉，mx 偏小、答案偏大。还有把答案当成窗口里最多的 1，方向反了——要的是换掉的 0 的个数，是 k 减 mx，不是 mx。环形已相邻、没有 1、全是 1 这几种都不用换，答案是 0。

Python

from __future__ import annotations
from typing import *
from collections import *
from functools import *
from itertools import *
from math import *
from heapq import *
from bisect import *
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

C++

#include <algorithm>
#include <array>
#include <cctype>
#include <climits>
#include <cmath>
#include <deque>
#include <functional>
#include <iostream>
#include <limits>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>
using namespace std;
class Solution {
public:
    int minSwaps(vector<int>& nums) {
        int k = accumulate(nums.begin(), nums.end(), 0);
        int n = nums.size();
        int cnt = accumulate(nums.begin(), nums.begin() + k, 0);
        int mx = cnt;
        for (int i = k; i < n + k; ++i) {
            cnt += nums[i % n] - nums[(i - k + n) % n];
            mx = max(mx, cnt);
        }
        return k - mx;
    }
};

Java

import java.util.*;
class Solution {
    public int minSwaps(int[] nums) {
        int k = Arrays.stream(nums).sum();
        int n = nums.length;
        int cnt = 0;
        for (int i = 0; i < k; ++i) {
            cnt += nums[i];
        }
        int mx = cnt;
        for (int i = k; i < n + k; ++i) {
            cnt += nums[i % n] - nums[(i - k + n) % n];
            mx = Math.max(mx, cnt);
        }
        return k - mx;
    }
}