排布二进制网格的最少交换次数 图解题解
这道题到底在问什么
- 输入
- grid=[[0,0,1],[1,1,0],[1,0,0]]
- 输出
- 3
- 输入
- grid=[[1,0,0],[1,1,0],[1,1,1]]
- 输出
- 0
最优解：一步一步想明白
- 3记住这套打法:先数每行末尾连续 0 的个数,再从上到下给每个位置就近找一个够格的行冒泡上来,交换次数累加距离,中途找不到就是 -1。下面先把三行的末尾 0 都数出来。
- 4橙=待安排,灰=已就位这就是 3 行 3 列的网格。先看要求面板:位置 0 末尾要有 ≥ 2 个 0,位置 1 要 ≥ 1 个,位置 2 要 ≥ 0 个,也就是位置越靠上、末尾要的 0 越多。咱们先把每一行末尾连着几个 0 数出来。
- 5高亮=主对角线右上方,要求全 0高亮的这几个格子就是主对角线右上方的区域,合格网格要它们全为 0。第 0 行有两个、第 1 行有一个、第 2 行一个都没有。一行末尾连着的 0 越多,就越能盖住右上方这片,所以越要往上放。
- 6这一行末尾0 = 0看第 0 行 0、0、1,从右往左数,碰到第一个 1 就停。它末尾连着的 0 有 0 个。接着数下一行。
- 7这一行末尾0 = 1看第 1 行 1、1、0,从右往左数,碰到第一个 1 就停。它末尾连着的 0 有 1 个。接着数下一行。
- 8这一行末尾0 = 2看第 2 行 1、0、0,从右往左数,碰到第一个 1 就停。它末尾连着的 0 有 2 个。三行都数完了,末尾0 分别是 0、1、2。
- 9需求 2 / 1 / 0,现在还对不上三行末尾0 从上到下是 0、1、2,而位置 0、1、2 的需求是 2、1、0,正好反着来。现在从最上面的位置开始安排,需求最高的放最上面。
- 10在位置 0 及其下方找最近的够格行现在轮到位置 0,它需要末尾0 不少于 2 个。就从位置 0 自己开始往下看,找最近的、末尾0 够 2 的那一行。
- 11末尾0 0 不足 2,跳过第 0 行末尾0 只有 0,不到 2,盖不住位置 0 右上方的格子,跳过它,继续往下看。
- 12末尾0 1 不足 2,跳过第 1 行末尾0 只有 1,不到 2,盖不住位置 0 右上方的格子,跳过它,继续往下看。
- 13够格,选它冒泡到位置 0第 2 行末尾0 是 2,达到了 2,够格。它离位置 0 有 2 步,要用 2 次相邻交换把它一格一格冒泡上来。总交换次数先加上 2。
- 14继续往上冒泡把它和上面那一行对调一次,它就往上挪了一格,现在到了第 1 行。还没到位置 0,再换一次。
- 15够格行已到位置 0把它和上面那一行对调一次,它就往上挪了一格,现在到了第 0 行。正好落到位置 0,这一轮的交换做完了。
- 16累计交换 2位置 0 安排好了,这一行末尾0 是 2,满足 ≥ 2,右上方该为 0 的格子都盖住了。它就此锁定,后面的安排只在它下面进行。累计交换到现在是 2 次。
- 17在位置 1 及其下方找最近的够格行现在轮到位置 1,它需要末尾0 不少于 1 个。就从位置 1 自己开始往下看,找最近的、末尾0 够 1 的那一行。
- 18末尾0 0 不足 1,跳过第 1 行末尾0 只有 0,不到 1,盖不住位置 1 右上方的格子,跳过它,继续往下看。
- 19够格,选它冒泡到位置 1第 2 行末尾0 是 1,达到了 1,够格。它离位置 1 有 1 步,要用 1 次相邻交换把它一格一格冒泡上来。总交换次数先加上 1。
- 20够格行已到位置 1把它和上面那一行对调一次,它就往上挪了一格,现在到了第 1 行。正好落到位置 1,这一轮的交换做完了。
- 21累计交换 3位置 1 安排好了,这一行末尾0 是 1,满足 ≥ 1,右上方该为 0 的格子都盖住了。它就此锁定,后面的安排只在它下面进行。累计交换到现在是 3 次。
- 22在位置 2 及其下方找最近的够格行现在轮到位置 2,它需要末尾0 不少于 0 个。就从位置 2 自己开始往下看,找最近的、末尾0 够 0 的那一行。这次需求是 0,任何行都够格。
- 23够格,选它冒泡到位置 2第 2 行末尾0 是 0,达到了 0,够格。它离位置 2 有 0 步,本来就在位置上,不用交换。总交换次数先加上 0。
- 24累计交换 3位置 2 安排好了,这一行末尾0 是 0,满足 ≥ 0,右上方该为 0 的格子都盖住了。它就此锁定,后面的安排只在它下面进行。累计交换到现在是 3 次。
- 25主对角线右上方已全为 0三个位置都安排妥当,回看整张网格,主对角线右上方的格子全是 0,合格了。一路上做了 2 次再加 1 次相邻交换,一共 3 次,这就是最少交换次数,答案 3。
⚠️ 容易写错的地方
✗ 错：把主对角线本身也要求为 0
✓ 对：只要求严格在对角线右上方的格子为 0
第 i 行只管第 i+1 列往右,第 i 列自己以及左边随便,所以位置 i 的需求是 n-1-i 不是 n-i
✗ 错：末尾0 误数成整行 0 的总数
✓ 对：只数从右端起连续的 0,碰到第一个 1 就停
像 1、0、1、0、0 末尾连续 0 只有 2 个,中间那个 0 被 1 挡住不算
✗ 错：贪心去抢末尾0 最多的那一行
✓ 对：要选最近的、刚好够格的那一行
就近上移交换代价最小;被换下来的更远够格行放到更靠下的位置,那里需求更低,它照样够格,不影响后续
✗ 错：以为能直接跨行交换
✓ 对：每次只能换相邻两行,代价就是距离
把第 j 行挪到第 i 行要 j 减 i 次相邻交换,答案累加的正是这个距离之和
完整代码（Python / C++ / Java）
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 ansC++
#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;
}
}复杂度
时间
O(n²)
n 是网格边长。先求每行的 pos 要把每行从右往左扫,最坏是 O(n²);贪心阶段有 n 个位置,每个位置往下找够格行最多看 O(n) 行、冒泡又最多 O(n) 次相邻交换,合起来也是 O(n²)。整体由这两段平方主导,是 O(n²)
空间
O(n)
只额外开了一个长度为 n 的 pos 数组,记每行最右 1 的列号,按峰值就是 O(n)。没有按网格面积 n² 去开额外空间,交换是在原数组上原地进行
看不够？换成动画再走一遍
上面的推演每一步都对应一帧动画。点开交互动画版，能一步步看着 排布二进制网格的最少交换次数 的数据怎么变、指针怎么走，还能切 Python / Java / C++ 跟着练。
面试官可能追问
为什么就近上移这个贪心一定最优,不会错过更省的方案?+
可以用交换论证。位置 i 必须放一个末尾 0 够 n-1-i 的行,假设最优解放的不是最近那个够格行,而是更远的一个。那么最近那个够格行此刻还压在下面,把这两个的角色对调,让最近的上去、远的留下,最近够格行上移的距离不超过更远那行,交换代价只会更短或持平。关键在于,那行更远的够格行既然能被原方案放到位置 i,就说明它末尾 0 至少满足位置 i 的需求;如今把它留到更靠下、需求更松的位置,只会更容易满足,所以照样合格。这样一步步调整,总能把任何最优解掰成「每个位置都取最近够格行」的样子而代价不增,所以就近贪心一定最优。
把每行的末尾 0 个数求得更快有没有办法?+
本身从右往左扫一行碰到第一个 1 就停,最坏才到 O(n);把所有行加起来是 O(n²),已经和后面贪心同量级,不是瓶颈,通常不必再优化。真要抠常数,可以在读入每行时顺手记下最右 1 的列号,一遍就出结果,省掉单独再扫一趟。
这道题和「把数组排成目标顺序的最少相邻交换次数」是不是一类?+
本质相通。相邻交换把一行挪到目标位,代价等于它移动的距离,这跟用相邻交换排序、代价是逆序对个数是同一套思想。不同的是这里不要求完全排成某个固定顺序,只要每个位置的行末尾 0 够用即可,所以用贪心就近取,而不是去数逆序对,但「相邻交换代价等于距离」这个核心是一样的。
想听吴师兄把这道题讲给你听？
文字版和动画都随便看。开通图解算法年卡，可以听吴师兄声线把 排布二进制网格的最少交换次数 一步步讲透（全站 0 节语音精讲，持续扩充）， 卡住的地方还有 AI 私教小欧就着动画帮你拆到懂。
本平台为独立第三方培训机构，与华为技术有限公司无任何关联；课程的服务内容与权益以购买协议为准，学习效果因个人情况而异。「华为 OD」「华为可信」等仅为对岗位与考试方向的客观描述，相关商标归各自权利人所有。