排布二进制网格的最少交换次数 图解题解

网格要摆成什么样才算合格

给一个 n 行 n 列、只含 0 和 1 的网格，每次只能交换相邻两行，最少换几次能让主对角线右上方全为 0，做不到返回 −1。右上方指第 i 行第 i+1 列往右的格子，对角线和左边随便，也就是第 i 行末尾得有足够多连着的 0，位置越靠上需要的越多。

挨个试所有行排法为什么走不通

n 行有 n! 种先后顺序，全排开检查哪些合法、再挑交换最少的，n 才十几就爆了。而且每次只能换相邻两行，把一行挪到目标位得逐格挪，代价是移动距离。得找条不枚举全排列的路。

先数每行末尾的 0，就近挑一行上移

每行并不用摆到某个确定名次，只要末尾连续的 0 够盖住它所在位置的右上方就行。先量每行末尾连着几个 0，从右端往左数、碰到第一个 1 就停；位置 i 需要 n−1−i 个，谁够多谁往上放。

参考代码里换了个等价的量，记每行最右那个 1 在第几列、存进 pos 数组，末尾连续 0 就是 n−1 减去这列号，整行全 0 记 −1。位置 i 要末尾 0 够 n−1−i 个，换成列号看就是最右的 1 落在第 i 列或更左，两把尺子等价。之后就近取够格的行冒上来，总交换最省。

从上到下逐个位置安排够格的行

从位置 0 排到位置 n−1。轮到位置 i，从第 i 行起往下找第一个够格的行，记作第 j 行，把它一步步和上面相邻行对调、冒到第 i 位，一共 j−i 次交换累加进答案，被挤过的行整体下移一格。

冒上来的行就此锁定，就近取第一个不会亏：被换下的那些末尾 0 更多的行，落到更靠下、需求更松的位置照样够用。从第 i 行往下找不到够格的就返回 −1。

拿题面这张 3×3 网格从头排一遍

用题面的 grid=[[0,0,1],[1,1,0],[1,0,0]]，答案 3。数末尾 0：第 0 行 0、0、1 从右往左碰到第一个 1 就停、有 0 个；第 1 行 1、1、0 有 1 个；第 2 行 1、0、0 有 2 个。三行从上到下是 0、1、2。

位置 0 要不少于 2 个：前两行的 0 和 1 都不够，第 2 行的 2 个够格、离位置 0 有 2 步，累加 2、冒到顶，末尾 0 成 2、0、1。位置 1 要不少于 1 个：紧挨的行是 0 不够，下一行 1 够格、隔 1 步，累加 1，末尾 0 成 2、1、0。位置 2 只要 0 个、当前行本就 0 步。合计 2 加 1 加 0，答案 3。

末尾 0 只数右端连续段，别贪最多的行

求每行末尾 0 从右往左扫是 O(n²)；贪心阶段 n 个位置、每个往下找够格行和冒泡各最多 O(n) 次，也是 O(n²)。只额外开长度为 n 的数组记每行最右的 1，原地交换，空间 O(n)。

几个边界：单行网格没有右上方格子、天然合格，0 次；整张全 0 每行都管够，也 0 次；某位置往下凑不出够格行就返回 −1。最常写坏的：对角线那格不要求为 0，需求是 n−1−i 不是 n−i；末尾 0 只数右端连续那段，像 1、0、1、0、0 中间的 0 被 1 挡着不算、只有 2 个；也别去抢末尾 0 最多的行，挑最近刚够格的。

Python

from __future__ import annotations
from typing import *
from collections import *
from functools import *
from itertools import *
from math import *
from heapq import *
from bisect import *
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:
                return -1
            while k > i:
                pos[k], pos[k - 1] = pos[k - 1], pos[k]
                k -= 1
        return ans

C++

#include <algorithm>
#include <array>
#include <cctype>
#include <climits>
#include <cmath>
#include <deque>
#include <functional>
#include <iostream>
#include <limits>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>
using namespace std;
class Solution {
public:
    int minSwaps(vector<vector<int>>& grid) {
        int n = grid.size();
        vector<int> pos(n, -1);
        for (int i = 0; i < n; ++i) {
            for (int j = n - 1; j >= 0; --j) {
                if (grid[i][j] == 1) {
                    pos[i] = j;
                    break;
                }
            }
        }
        int ans = 0;
        for (int i = 0; i < n; ++i) {
            int k = -1;
            for (int j = i; j < n; ++j) {
                if (pos[j] <= i) {
                    ans += j - i;
                    k = j;
                    break;
                }
            }
            if (k == -1) {
                return -1;
            }
            for (; k > i; --k) {
                swap(pos[k], pos[k - 1]);
            }
        }
        return ans;
    }
};

Java

import java.util.*;
class Solution {
    public int minSwaps(int[][] grid) {
        int n = grid.length;
        int[] pos = new int[n];
        Arrays.fill(pos, -1);
        for (int i = 0; i < n; ++i) {
            for (int j = n - 1; j >= 0; --j) {
                if (grid[i][j] == 1) {
                    pos[i] = j;
                    break;
                }
            }
        }
        int ans = 0;
        for (int i = 0; i < n; ++i) {
            int k = -1;
            for (int j = i; j < n; ++j) {
                if (pos[j] <= i) {
                    ans += j - i;
                    k = j;
                    break;
                }
            }
            if (k == -1) {
                return -1;
            }
            for (; k > i; --k) {
                int t = pos[k];
                pos[k] = pos[k - 1];
                pos[k - 1] = t;
            }
        }
        return ans;
    }
}