Medium

题目描述

给你一个 n x n 的二进制网格，每一次操作中，你可以选择网格的相邻两行，交换它们。

如果网格的所有主对角线以上的格子全部都是 0，则认为该网格是合法的。

请你返回使网格变成合法状态的最小交换次数，如果无法使网格合法，请返回 -1。

网格的主对角线是指从 (1, 1) 到 (n, n) 的那条对角线。

示例 1：

输入：grid = [[0,0,1],[1,1,0],[1,0,0]]
输出：3

示例 2：

输入：grid = [[0,1,1,0],[0,1,1,0],[0,1,1,0],[0,1,1,0]]
输出：-1
解释：所有行都相似，交换相邻行无效。

示例 3：

输入：grid = [[1,0,0],[1,1,0],[1,1,1]]
输出：0

提示：

  • n == grid.length == grid[i].length
  • 1 <= n <= 200
  • grid[i][j] 要么是 0，要么是 1

解题思路

这道题需要将二进制网格排列成主对角线以上全为0的形状。关键观察是：要使主对角线以上全为0，第i行(从0开始)必须从第i列开始往右全为0，也就是说第i行的最后一个1不能出现在第i列或之后。

解题思路：

  1. 计算每行的最右边1的位置：遍历每一行，记录最后一个1出现的位置。如果某行全为0，则记录为-1。

  2. 检查是否有解：对于第i行（从0开始），其最后一个1的位置必须小于i。我们可以通过贪心策略验证：将所有行按照最后一个1的位置排序，检查排序后的第i行是否满足条件。

  3. 模拟交换过程：如果有解，我们需要通过相邻交换将行重新排列。对于每个位置i，找到第一个满足条件的行（最后一个1的位置小于i），然后通过相邻交换将其移动到位置i。

  4. 计算交换次数：每次将目标行通过相邻交换移动到正确位置，累计交换次数。

这是一个贪心算法，时间复杂度主要来自于寻找合适的行和执行交换操作。

代码实现

class Solution {
public:
    int minSwaps(vector<vector<int>>& grid) {
        int n = grid.size();
        vector<int> lastOne(n);
        
        // 计算每行最后一个1的位置
        for (int i = 0; i < n; i++) {
            lastOne[i] = -1;
            for (int j = n - 1; j >= 0; j--) {
                if (grid[i][j] == 1) {
                    lastOne[i] = j;
                    break;
                }
            }
        }
        
        // 检查是否有解
        vector<int> sorted = lastOne;
        sort(sorted.begin(), sorted.end());
        for (int i = 0; i < n; i++) {
            if (sorted[i] > i) {
                return -1;
            }
        }
        
        // 模拟交换过程
        int swaps = 0;
        for (int i = 0; i < n; i++) {
            // 找到第一个满足条件的行
            int target = -1;
            for (int j = i; j < n; j++) {
                if (lastOne[j] <= i) {
                    target = j;
                    break;
                }
            }
            
            // 将target行移动到位置i
            while (target > i) {
                swap(lastOne[target], lastOne[target - 1]);
                target--;
                swaps++;
            }
        }
        
        return swaps;
    }
};

class Solution:
    def minSwaps(self, grid: List[List[int]]) -> int:
        n = len(grid)
        last_one = []
        
        # 计算每行最后一个1的位置
        for i in range(n):
            pos = -1
            for j in range(n - 1, -1, -1):
                if grid[i][j] == 1:
                    pos = j
                    break
            last_one.append(pos)
        
        # 检查是否有解
        sorted_pos = sorted(last_one)
        for i in range(n):
            if sorted_pos[i] > i:
                return -1
        
        # 模拟交换过程
        swaps = 0
        for i in range(n):
            # 找到第一个满足条件的行
            target = -1
            for j in range(i, n):
                if last_one[j] <= i:
                    target = j
                    break
            
            # 将target行移动到位置i
            while target > i:
                last_one[target], last_one[target - 1] = last_one[target - 1], last_one[target]
                target -= 1
                swaps += 1
        
        return swaps

public class Solution {
    public int MinSwaps(int[][] grid) {
        int n = grid.Length;
        int[] lastOne = new int[n];
        
        // 计算每行最后一个1的位置
        for (int i = 0; i < n; i++) {
            lastOne[i] = -1;
            for (int j = n - 1; j >= 0; j--) {
                if (grid[i][j] == 1) {
                    lastOne[i] = j;
                    break;
                }
            }
        }
        
        // 检查是否有解
        int[] sorted = new int[n];
        Array.Copy(lastOne, sorted, n);
        Array.Sort(sorted);
        for (int i = 0; i < n; i++) {
            if (sorted[i] > i) {
                return -1;
            }
        }
        
        // 模拟交换过程
        int swaps = 0;
        for (int i = 0; i < n; i++) {
            // 找到第一个满足条件的行
            int target = -1;
            for (int j = i; j < n; j++) {
                if (lastOne[j] <= i) {
                    target = j;
                    break;
                }
            }
            
            // 将target行移动到位置i
            while (target > i) {
                int temp = lastOne[target];
                lastOne[target] = lastOne[target - 1];
                lastOne[target - 1] = temp;
                target--;
                swaps++;
            }
        }
        
        return swaps;
    }
}

var minSwaps = function(grid) {
    const n = grid.length;
    
    // Calculate trailing zeros for each row
    const trailingZeros = [];
    for (let i = 0; i < n; i++) {
        let zeros = 0;
        for (let j = n - 1; j >= 0; j--) {
            if (grid[i][j] === 0) {
                zeros++;
            } else {
                break;
            }
        }
        trailingZeros.push(zeros);
    }
    
    let swaps = 0;
    
    // For each position, find a row that satisfies the requirement
    for (let i = 0; i < n; i++) {
        const required = n - 1 - i;
        
        // Check if current row already satisfies
        if (trailingZeros[i] >= required) {
            continue;
        }
        
        // Find the next row that satisfies
        let found = false;
        for (let j = i + 1; j < n; j++) {
            if (trailingZeros[j] >= required) {
                // Move this row to position i
                while (j > i) {
                    // Swap with previous row
                    [trailingZeros[j], trailingZeros[j - 1]] = [trailingZeros[j - 1], trailingZeros[j]];
                    j--;
                    swaps++;
                }
                found = true;
                break;
            }
        }
        
        if (!found) {
            return -1;
        }
    }
    
    return swaps;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型值
时间复杂度O(n²)
空间复杂度O(n)

时间复杂度分析：

  • 计算每行最后一个1的位置：O(n²)
  • 检查是否有解（排序）：O(n log n)
  • 模拟交换过程：最坏情况下每行都需要移动到开头，总共O(n²)次交换
  • 总体时间复杂度：O(n²)

空间复杂度分析：

  • 存储每行最后一个1的位置：O(n)
  • 排序时的额外空间：O(n)
  • 总体空间复杂度：O(n)