题目描述
思路解析动画文字版
记牢这套路:第一步查同余定生死,第二步排序取中位数当目标,第三步把每个数到中位数的距离除以 x 累加。下面从拍扁网格开始。
输入网格 · x = 2：这就是我们的输入,一张 3 行 3 列的网格,右上角记着 x 等于 2。每次操作能给任意一个格子加 2 或减 2。你先扫一眼这 9 个数,全是偶数。接下来第一件事,是把这张二维网格拍扁成一条一维的数,处理起来更顺手。
把网格一行一行读下来,拉成一条一维数组:8、2、6、4、10、8、6、4、2,一共 9 个数。位置怎么排其实无所谓,因为最后只关心它们各自离目标有多远。拍扁之后,先别急着算,得先回答一个生死问题:这些数到底能不能凑到同一个值上。
从第 0 个数 8 开始。参考代码拿它除以 x 的余数当作基准:8 除以 2 余 0,于是把 mod 定成 0。之后每一个数都要拿来和这个 0 对比,只要有一个余数不是 0,整张网格就没救了。
轮到第 1 个数 2,除以 2 余 0,正好等于基准 mod 的 0,过关。它和 8 之间相差的是 2 的整数倍,理论上能靠若干次加减 2 走到一块去。绿色表示这个数已经通过同余检查。
轮到第 2 个数 6,除以 2 余 0,正好等于基准 mod 的 0,过关。它和 8 之间相差的是 2 的整数倍,理论上能靠若干次加减 2 走到一块去。绿色表示这个数已经通过同余检查。
轮到第 3 个数 4,除以 2 余 0,正好等于基准 mod 的 0,过关。它和 8 之间相差的是 2 的整数倍,理论上能靠若干次加减 2 走到一块去。绿色表示这个数已经通过同余检查。
轮到第 4 个数 10,除以 2 余 0,正好等于基准 mod 的 0,过关。它和 8 之间相差的是 2 的整数倍,理论上能靠若干次加减 2 走到一块去。绿色表示这个数已经通过同余检查。
轮到第 5 个数 8,除以 2 余 0,正好等于基准 mod 的 0,过关。它和 8 之间相差的是 2 的整数倍,理论上能靠若干次加减 2 走到一块去。绿色表示这个数已经通过同余检查。
轮到第 6 个数 6,除以 2 余 0,正好等于基准 mod 的 0,过关。它和 8 之间相差的是 2 的整数倍,理论上能靠若干次加减 2 走到一块去。绿色表示这个数已经通过同余检查。
轮到第 7 个数 4,除以 2 余 0,正好等于基准 mod 的 0,过关。它和 8 之间相差的是 2 的整数倍,理论上能靠若干次加减 2 走到一块去。绿色表示这个数已经通过同余检查。
轮到第 8 个数 2,除以 2 余 0,正好等于基准 mod 的 0,过关。它和 8 之间相差的是 2 的整数倍,理论上能靠若干次加减 2 走到一块去。绿色表示这个数已经通过同余检查。
9 个数全部检查完,除以 2 的余数清一色是 0,同余成立,这张网格一定能变成单值,不用返回 -1。生死关过了,接下来才是正题:选一个共同目标,让总操作数最少。
把这 9 个数从小到大排好,变成 2、2、4、4、6、6、8、8、10。排序是为了下一步好取中位数。你可能会问,为什么不直接取平均值当目标,先按住这个疑问,等会儿有一帧专门算给你看,平均值反而更亏。
取正中间那个数当目标。9 个数,下标从 0 到 8,中间是下标 4,值是 6。参考代码里就写成 nums 长度右移一位,也就是 9 除以 2 取整等于 4。把 6 定为大家要一起走到的目标值。下面挨个算,每个数走到 6 要几步。
看下标 0 这个数 2。它和目标 6 相差 4,而每次操作动 2,所以 要加 2 次 2,折合 2 次操作。把 2 加进累计,现在 ops 等于 2。蓝色的都是已经结算过的数。
看下标 1 这个数 2。它和目标 6 相差 4,而每次操作动 2,所以 要加 2 次 2,折合 2 次操作。把 2 加进累计,现在 ops 等于 4。蓝色的都是已经结算过的数。
看下标 2 这个数 4。它和目标 6 相差 2,而每次操作动 2,所以 要加 1 次 2,折合 1 次操作。把 1 加进累计,现在 ops 等于 5。蓝色的都是已经结算过的数。
看下标 3 这个数 4。它和目标 6 相差 2,而每次操作动 2,所以 要加 1 次 2,折合 1 次操作。把 1 加进累计,现在 ops 等于 6。蓝色的都是已经结算过的数。
看下标 4 这个数 6。它和目标 6 相差 0,而每次操作动 2,所以 本身就是 6,不用动,折合 0 次操作。把 0 加进累计,现在 ops 等于 6。蓝色的都是已经结算过的数。
看下标 5 这个数 6。它和目标 6 相差 0,而每次操作动 2,所以 本身就是 6,不用动,折合 0 次操作。把 0 加进累计,现在 ops 等于 6。蓝色的都是已经结算过的数。
看下标 6 这个数 8。它和目标 6 相差 2,而每次操作动 2,所以 要减 1 次 2,折合 1 次操作。把 1 加进累计,现在 ops 等于 7。蓝色的都是已经结算过的数。
看下标 7 这个数 8。它和目标 6 相差 2,而每次操作动 2,所以 要减 1 次 2,折合 1 次操作。把 1 加进累计,现在 ops 等于 8。蓝色的都是已经结算过的数。
看下标 8 这个数 10。它和目标 6 相差 4,而每次操作动 2,所以 要减 2 次 2,折合 2 次操作。把 2 加进累计,现在 ops 等于 10。蓝色的都是已经结算过的数。
9 个数全部结算完,把它们各自走到 6 需要的次数加起来,一共是 10。这就是把整张网格变成单值网格的最少操作数。回头看整条链路:先判同余保证有解,再排序取中位数当目标,最后把每个数的距离折算成次数求和,答案 10。
边界先想清:单格恒为 0、余数不同返回 -1、已经全相等也是 0。
面试重点:同余判可行、排序取中位数、距离和求答案;中位数最优可用挪动目标的增减论证;时间 O(mn log(mn))、空间 O(mn)。
参考代码
from __future__ import annotationsfrom typing import *from collections import *from functools import *from itertools import *from math import *from heapq import *from bisect import *class Solution: def minOperations(self, grid: List[List[int]], x: int) -> int: nums = [] mod = grid[0][0] % x for row in grid: for v in row: if v % x != mod: return -1 nums.append(v) nums.sort() mid = nums[len(nums) >> 1] return sum(abs(v - mid) // x for v in nums)复杂度
- 时间：O(mn log(mn))，m 行 n 列共 mn 个数。同余检查和距离求和都是扫一遍 O(mn),真正主导的是中间那次排序,量级 O(mn log(mn))
- 空间：O(mn)，按峰值算。要把网格拍扁存进一维数组,占 O(mn)。排序内部另有栈开销:C++ 与 Java 约 O(log(mn)) 递归栈,Python 的 Timsort 最坏 O(mn),都不超过数组本身量级
易错点
面试追问把动画讲成自己的话
追问这题的核心思路是什么?
追问为什么共同目标一定要取中位数,能证明吗?
追问复杂度是多少?
这道题到这就讲完了。动画和文字是同一套思路——别光看，关掉页面自己默写一遍。然后顺着主线继续：
从给定原材料中找到所有可以做出的菜
LeetCode 2115 · 中等 · 沿着 图论套路 继续往下推进
把这道题真正学会，再走
图解算法年卡 ¥99 /年
- ✓本题每步动画的吴师兄语音讲解（全站陆续覆盖）
- ✓小欧带 8 步通关训练——追问到不看答案也能写对、能 30 秒讲给面试官听
- ✓学习报告，记录每道题的掌握程度
76k+ GitHub Star · 吴师兄开源图解算法，几十万开发者在看的算法讲解
想成体系刷透这类套路？去图解算法专题