难度: Medium
给你一个 n x n 的二进制网格 grid，每一次操作中，你可以选择网格的 相邻两行 进行交换。
一个符合要求的网格需要满足主对角线以上的格子全部都是 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.lengthn == grid[i].length1 <= n <= 200grid[i][j] 要么是 0 要么是 1 。运行时间: 43 ms
内存: 17.5 MB
class Solution:
def minSwaps(self, grid: List[List[int]]) -> int:
n = len(grid)
pos = [-1] * n
for i in range(n):
for j in range(n - 1, -1, -1):
if grid[i][j] == 1:
pos[i] = j
break
ans = 0
for i in range(n):
k = -1
for j in range(i, n):
if pos[j] <= i:
ans += j - i
k = j
break
if k != -1:
for j in range(k, i, -1):
pos[j], pos[j - 1] = pos[j - 1], pos[j]
else:
return -1
return ans
此题解首先对每一行计算从最后一个元素开始到第一个1的位置，存储在数组pos中。然后，遍历这个pos数组，尝试将每个行的最后一个1移动到对角线以下的合适位置。如果某行的最后一个1的位置超过了其行号，则需要通过交换行来调整位置。对于每一个目标行i，从i开始向下查找可以移动到该行的1的最大位置的行，记录交换次数，然后进行实际的行交换。如果找不到可以交换的行，返回-1。否则，返回总的交换次数。
时间复杂度: O(n^2)
空间复杂度: O(n)
class Solution:
def minSwaps(self, grid: List[List[int]]) -> int:
n = len(grid)
pos = [-1] * n
# 计算每一行最右边的1的位置
for i in range(n):
for j in range(n - 1, -1, -1):
if grid[i][j] == 1:
pos[i] = j
break
ans = 0
# 对每行进行检查和可能的行交换
for i in range(n):
k = -1
# 查找可以移动到行i的行
for j in range(i, n):
if pos[j] <= i:
ans += j - i
k = j
break
# 执行行交换
if k != -1:
for j in range(k, i, -1):
pos[j], pos[j - 1] = pos[j - 1], pos[j]
else:
return -1
return ans
这种方法主要用于快速确定每行1的分布情况，以便于后续的行交换操作。在这个问题中，我们需要将每行的最右边的1尽可能地靠近对角线，如果知道每行1的最右边位置，就能判断哪些行需要通过交换来调整位置，从而实现整个矩阵的最优布局。这种方法能有效地简化问题，减少不必要的比较和交换次数。
选择从每行的最后一个元素向前查找是因为我们关心的是每行最右边的1的位置。从后向前查找可以更快地找到这个位置，一旦找到，即可停止该行的进一步搜索，节省了时间。如果从前向后查找，则需要遍历整行才能确保找到最右边的1，效率较低。
在本题中，我们的目标是尽量使每行从对角线开始到行末都是0。如果某行的最后一个1的位置超过了其行号，说明该1无法直接移到对角线上，因为对角线上对应的位置已经需要是0。因此，必须通过行交换，将这样的行与下面的某行（其最后一个1的位置不超过当前行号的行）交换，以确保每行最右边的1尽可能靠近或在对角线上。
选择一旦找到就停止查找的策略是为了最小化行交换次数。我们从当前行开始向下查找首个满足条件的行，因为这样可以保证交换次数最少（即尽可能少的向下滑动行）。如果继续查找可能会找到更远的行，但这将导致更多的交换次数。因此，这种策略是为了保证找到的解是交换次数最少的，从而实现最优解。