---

1536. 排布二进制网格的最少交换次数

• 标签：贪心、数组、矩阵
• 难度：中等

题目链接

• 1536. 排布二进制网格的最少交换次数 - 力扣

题目大意

描述：给定一个 $n \times n$ 的二进制矩阵 $grid$。每次操作可以交换相邻两行。

要求：返回使得矩阵满足"主对角线右上方的所有元素都是 $0$"所需的最少交换次数。如果无法做到，返回 $-1$。

说明：主对角线右上方指 $grid[i][j] = 0$ 对于所有 $i < j$。即每行从右往左数的连续 $0$ 的个数有一定要求。

示例：

• 示例 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
解释：所有行都是一样的，交换相邻行无法使网格符合要求。

解题思路

思路 1：贪心

1. 核心思想

对于第 $i$ 行（从上到下，$0$-based），要求该行从右侧开始至少有 $n - i - 1$ 个连续的 $0$（即 $grid[i][n-1-(n-i-1)+1] = grid[i][i+1]$ 到行尾都是 $0$）。

换句话说，第 $0$ 行要求最后 $n-1$ 个元素全为 $0$，第 $1$ 行要求最后 $n-2$ 个元素全为 $0$，...，第 $n-2$ 行要求最后 $1$ 个元素为 $0$，第 $n-1$ 行没有要求。

先计算每行从右往左的连续 $0$ 的个数 $zeros[i]$。然后对于每行 $i$（从 $0$ 到 $n-1$），找一个满足 $zeros[j] \ge n - i - 1$ 的最靠上的行 $j$（$j \ge i$），将 $j$ 行交换到 $i$ 行，交换次数为 $j - i$。

2. 具体步骤

第 1 步：计算每行的后缀 $0$ 个数 $right\_zeros[i]$。

第 2 步：创建一个标记数组 $used$。

第 3 步：从 $i = 0$ 到 $n-1$：

• 找最小的 $j \ge i$ 使得 $right\_zeros[j] \ge n - i - 1$ 且 $!used[j]$。
• 如果找不到，返回 $-1$。
• 将 $j$ 移到 $i$：（此处的交换需要通过将 $j$ 与上方的行依次交换，但我们可以直接计算交换次数）。
• 标记 $used[j] = True$。

第 4 步：累计交换次数。

3. 交换次数的计算

如果选择将第 $j$ 行交换到第 $i$ 行（$j \ge i$），需要 $j - i$ 次交换（逐行向上交换）。但需要注意，后面的选择会影响前面的结果。

更简单的实现：每次找到需要的行 $j$ 后，从 $j$ 开始向上冒泡交换到 $i$，同时更新 $right\_zeros$ 数组。

ans = 0
for i in range(n):
    if right_zeros[i] >= n - i - 1:
        continue
    j = i + 1
    while j < n and right_zeros[j] < n - i - 1:
        j += 1
    if j == n:
        return -1
    # 将 j 行向上交换到 i
    for k in range(j, i, -1):
        right_zeros[k], right_zeros[k-1] = right_zeros[k-1], right_zeros[k]
        ans += 1

4. 举例说明

以 $grid = [[0,0,1],[1,1,0],[1,0,0]]$ 为例：

0 0 1   → 从右连续 0 数: 0
1 1 0   → 从右连续 0 数: 1
1 0 0   → 从右连续 0 数: 2

要求：第 $0$ 行需要 $\ge 2$ 个后缀 $0$，第 $1$ 行需要 $\ge 1$ 个。

• $i=0$：需要 $\ge 2$。第 $0$ 行只有 $0$ 个，找 $j=1$，$zeros[1]=1<2$，$j=2$，$zeros[2]=2 \ge 2$。将第 $2$ 行换到第 $0$ 行，交换次数 $2-0=2$。
• $i=1$：需要 $\ge 1$。现在第 $1$ 行（原第 $0$ 行）$zeros=0<1$，找 $j=2$（原第 $1$ 行）$zeros=1 \ge 1$。交换次数 $2-1=1$。
• $i=2$：需要 $\ge 0$。自动满足。

总交换次数 $= 2 + 1 = 3$。

思路 1：代码

class Solution:
    def minSwaps(self, grid: List[List[int]]) -> int:
        n = len(grid)
        # 计算每行从右开始的连续 0 个数
        zeros = [0] * n
        for i in range(n):
            cnt = 0
            for j in range(n - 1, -1, -1):
                if grid[i][j] == 0:
                    cnt += 1
                else:
                    break
            zeros[i] = cnt

        ans = 0
        for i in range(n):
            need = n - i - 1
            if zeros[i] >= need:
                continue
            # 找下面满足条件的行
            j = i + 1
            while j < n and zeros[j] < need:
                j += 1
            if j == n:
                return -1
            # 将第 j 行向上交换到第 i 行
            for k in range(j, i, -1):
                zeros[k], zeros[k - 1] = zeros[k - 1], zeros[k]
                ans += 1

        return ans

思路 1：复杂度分析

• 时间复杂度：$O(n^2)$，$n \le 300$，可行。
• 空间复杂度：$O(n)$。