題目資訊

• 題目編號: 1151
• 題目連結: Minimum Swaps to Group All 1’s Together
• 主題: Array, Sliding Window

題目敘述

給定一個二元陣列 data，返回將數組中所有 1 聚集在一起的最小交換次數。

範例 1:

輸入: data = [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:

輸入: data = [0,0,0,1,0]
輸出: 0
解釋: 由於數組中只有一個 1，所以不需要交換。

範例 3:

輸入: data = [1,0,1,0,1,0,0,1,1,0,1]
輸出: 3
解釋: 一個可能的解決方案是 [0,0,0,0,0,1,1,1,1,1,1]，使用 3 次交換。

約束條件:

$1 \leq \text{data.length} \leq 10^5$
$data[i]$ 只能是 0 或 1。

直覺

這個問題要求我們在二進位陣列中將所有的1進行分組，並且需要的交換次數最少。為了達成這個目標，我們需要一個有效的策略來計算必要的交換次數以合併所有的1。關鍵在於使用滑動窗口技術，其大小等於陣列中1的總數。此窗口將允許我們在陣列中滑動，並在窗口的每個位置計算當前的1的數量，從而能夠計算出使窗口內1的數量最大化所需的交換次數。

解法

1. 使用 accumulate 函數計算整個陣列中1的總數。這個值將用於確定滑動窗口的大小。

2. 初始化滑動窗口，計算大小為總1數量的第一個子陣列中的1的數量。這個初始窗口中的1的計數通過對陣列的初始部分求和來達成。

3. 通過從總1的數量中減去此初始窗口中的1的數量來計算初始所需的最小交換次數。這個結果代表了在起始位置達到一個完美包含所有1的窗口所需的交換次數。

4. 從左到右滑動窗口遍歷陣列。對於每一個新的窗口位置，通過減去前一個窗口的第一個元素，並加入序列中的下一個元素來更新1的數量。這步驟有效地將窗口轉移到右邊一個位置。

5. 對於每一個窗口位置，計算所需的交換次數，即用總1數量減去當前窗口中的1的數量。如果發現更小的交換次數，則更新最小交換次數。

6. 持續進行滑動窗口操作直到到達陣列的末尾，並返回所記錄的最小交換次數。

使用這種方法，我們透過管理和更新滑動窗口中的計數而不需多次重訪元素，達到了 $O(n)$ 的時間複雜度，確保即使是對於大的陣列也能保持最佳的性能。

程式碼

C++

class Solution {
public:
    int minSwaps(vector<int>& data) {

        // 計算陣列中所有1的總數。
        int totalOnes = accumulate(data.begin(), data.end(), 0);

        // 計算大小為`totalOnes`的第一個視窗中1的數量。
        int currentOnesInWindow = accumulate(data.begin(), data.begin() + totalOnes, 0);

        // 通過計算差異找出將所有1群組在一起所需的最小交換次數。
        int minSwapsNeeded = totalOnes - currentOnesInWindow;

        // 使用滑動視窗技巧檢查每個視窗來找出所需的最小交換次數。
        for (int i = 0; i < data.size() - totalOnes; i++) {
            // 通過減去超出的元素並加上新元素來更新當前視窗的計數。
            currentOnesInWindow += data[totalOnes + i] - data[i];

            // 計算當前視窗需要的交換次數，並在必要時更新最小交換次數。
            minSwapsNeeded = min(minSwapsNeeded, totalOnes - currentOnesInWindow);
        }

        return minSwapsNeeded;
    }
};

Python

class Solution:
    def minSwaps(self, data):

        # 計算陣列中 1 的總數。
        totalOnes = sum(data)

        # 計算大小為 `totalOnes` 的第一個窗口中 1 的數量。
        currentOnesInWindow = sum(data[:totalOnes])

        # 找出將所有 1 分組在一起所需的最小交換次數，透過計算差異。
        minSwapsNeeded = totalOnes - currentOnesInWindow

        # 使用滑動窗口技術來查找每個窗口所需的最小交換次數。
        for i in range(len(data) - totalOnes):
            # 更新當前窗口計數，扣除離開的元素並加入新的元素。
            currentOnesInWindow += data[totalOnes + i] - data[i]

            # 計算當前窗口所需的交換次數，並在必要時更新最小交換次數。
            minSwapsNeeded = min(minSwapsNeeded, totalOnes - currentOnesInWindow)

        return minSwapsNeeded

複雜度分析

• 時間複雜度: $O(n)$

  時間複雜度為 $O(n)$，因為該算法包含兩個主要迴圈，這兩個迴圈都會遍歷整個數組 data。第一次調用 accumulate 於 data 上來統計 1 的總數需要花費 $O(n)$ 的時間。第二次調用 accumulate 用來初始化第一個窗口中 1 的計數，這需要 $O(k)$ 的時間，其中 $k$ 是 1 的數量（小於或等於 $n$）。最後，for 迴圈遍歷數組的剩餘元素，更新滑動窗口，這個迴圈運行 $O(n-k)$ 次，共同維持 $O(n)$ 的複雜度。因此，總的時間複雜度是 $O(n)$。

• 空間複雜度: $O(1)$

  空間複雜度為 $O(1)$，因為該算法使用的額外空間量是恆定的，並不依賴於輸入的大小。像 totalOnes、currentOnesInWindow 和 minSwapsNeeded 等變數都是用來存儲整數的標量值，並且不需要隨著輸入數組大小而調整的額外數據結構。因此，空間複雜度是恆定的，即 $O(1)$。