1536. 排列二進制網格的最少交換次數

思路

給定一個方陣，每次可以交換兩個相鄰的列，要求最後滿足條件：主對角線以上的元素都是 0。 要求滿足條件所需的最小交換次數。

題目要求主對角線以上不可以有數字 1 存在，換句話說

• 對於第一列來說，數字 1 最後出現的位置，只允許在位置 0
• 對第二列來說，數字 1 最後出現的位置，只允許在位置 1
• $\dots$
• 對第 $i$ 列來說，數字 1 最後出現的位置，只允許在位置 $i - 1$

此時整個題目就變成了一個排序問題，把每一列最後一個 1 出現的位置記錄下來，
要找出滿足條件所需的最少交換次數。

每次只能交換「相鄰」的兩列，這個過程跟泡沫排序是一樣的，
所以整個過程可以視為「不完整」的泡沫排序。
之所以稱做「不完整」，是因為在完全排序好之前，
矩陣很可能就已經滿足條件，
而在滿足條件的當下，交換次數就是最少的。

因此我們能每次拿一個數字，找到最適合的位置，然後將它擺到那裏，把交換次數加入到答案當中。
不過這樣做會非常麻煩，具體有以下問題：

1. 如果交換nums[idx]到目標位置 nums[pos]，那麼交換過來的數字同樣需要經過比較。
2. 交換數字之後，所有在nums[idx], nums[pos]間的數字都要向左移動位置。
3. 被換到目標位置的數字，它的位置應該要標記被佔有，避免其他數字再度嘗試佔據這個位置。

每一列的要求，從上至下是越來越嚴苛的。
因此，我們不拿數字，而是拿「位置」去做配對，越前面的位置，要求越嚴格，
從整個數組挑最近的，滿足條件的數字，這能保證交換次數最少。

並且在pos被滿足之後，後續找滿足數字時，就不需要考慮前面已經被擺放的數字了。

程式碼

貪心

class Solution {
public:
    int minSwaps(vector<vector<int>>& grid) {
        int n = grid.size();
        vector<int> nums(n, -1); // 紀錄最後一個 1 出現的位置，預設 -1, 代表沒有出現
        for(int i = 0; i < n; i++) {
            for(int j = n - 1; j >= 0; j--) {
                if(grid[i][j] == 1) {
                    nums[i] = j;
                    break;
                }
            }
        }
        // 將位於 j 的數字往前移動到位置 i
        auto bubbleSwap = [&](int i, int j) -> int {
            for(int idx = j; idx > i; idx--) {
                swap(nums[idx], nums[idx - 1]);
            }
            return j - i;
        };
        int res = 0;
        for(int pos = 0; pos < n; pos++) {
            bool found = false;
            for(int i = pos; i < n; i++) {
                if(nums[i] <= pos) { // 可以擺，要最近
                    res += bubbleSwap(pos, i);
                    found = true;
                    break;
                }
            }
            if(!found) return -1;
        }
        return res;
    }
};

複雜度分析

• 時間複雜度：$O(n^2)$
• 空間複雜度：$O(n)$