Medium
Related Topics: Array / Sliding Window
LeetCode Source

解題想法

我們首先遍歷數組來計算1的總數。這個數據有兩個作用：

1. 有效處理邊界情況。
2. 決定滑動窗口的大小，因為它代表我們要形成的組的大小。

在一切開始前，我們先處理例外情況。如果數組中沒有1，或者所有元素都是1，則不需要任何交換。在這些情況下，我們可以立即返回0，節省不必要的計算。

接著，我們建立一個大小為 total 的初始窗口，並計算這個窗口中1的數量。這個窗口代表我們的第一個潛在段落，所有1都可以在其中分組。

我們使用兩個指針來滑動圓形數組中的窗口。滑動過程包括：

1. 移除窗口起始位置的元素。
2. 添加窗口末尾的下一個元素。

我們使用模運算符來圍繞數組進行滑動，模擬其圓形性質。

這樣可以在不創建重複數組或使用額外空間的情況下處理圓形特性。

在滑動窗口的過程中，我們追蹤任意窗口配置中看到的最多的1的數量。

這個最大值代表數組中已經連續存在的最大1的組。

在滑動窗口遍歷所有位置後，我們知道數組中連續存在的最大1的數量。

最小交換次數是總1的數量與這個最大值之間的差異。

這個差異代表需要移動以形成所有1的連續組的1的數量。

Complexity

Time Complexity: O(n)
Space Complexity: O(1)

Python

class Solution:
    def minSwaps(self, nums: List[int]) -> int:
        total, n, cur = 0, len(nums), 0

        for i in range(n):
            total += nums[i]

        if total == 0 or total == n:
            return 0

        for i in range(total):
            cur += nums[i]

        max_1 = cur

        for i in range(n):
            cur -= nums[i]
            cur += nums[(i + total) % n]
            max_1 = max(max_1, cur)

        return total - max_1

C++

class Solution {
public:
    int minSwaps(vector<int>& nums) {
        int n = nums.size();

        int total = 0;

        for (int i = 0; i < n; i++) {
            total += nums[i];
        }

        if (total == 0 || total == n)
            return 0;

        int cur = 0;

        for (int i = 0; i < total; i++)
            cur += nums[i];

        int max_1 = cur;

        for (int i = 0; i < n; i++) {
            cur -= nums[i];
            cur += nums[(i + total) % n];
            max_1 = max(cur, max_1);
        }

        return total - max_1;
    }
};