题目描述
思路解析
一句话答案：LeetCode 2033 获取单值网格的最小操作数：先查所有数除以 x 是否同余、不同就返回 -1，同余则排序取中位数当目标、每个数到中位数的距离除以 x 累加就是答案，而中位数让距离和最小，时间 O(mn log(mn))。
把整张网格变成同一个数，最少动几次
给一个 m 行 n 列的网格 grid 和整数 x，一次操作给任意一个格子加 x 或减 x，问最少几次能让所有格子相等，做不到返回 -1。题面第一个例子 grid=[[2,4],[6,8]]、x=2，答案是 4；第二个例子 grid=[[1,2],[3,4]]、x=2，答案是 -1——1、3 是奇数、2、4 是偶数，除以 2 余数不同，谁也走不到一块。
选平均值当目标、拿极差估次数，两条路都会崴
把 2、4、6、8 聚成一个数，平均值 5 每次只能加减 2、从偶数永远落不到奇数 5 上，何况它还常是小数，当不了目标。换成拿极差凑：最大 8 减最小 2 除以 2 得 3，可这只算了两端的账，中间的 4、6 要挪几步全漏了，凑不出总操作数。
余数对不齐就无解，对齐了中位数最省
先过生死关：一个格子每次变动都是 x 的整数倍，它能到达的值和自己除以 x 的余数永远一样。两个格子想最终相等，除以 x 的余数就必须相同。把所有数除以 x，余数只要有一个不同，这网格就没救、返回 -1；余数全相同，才有得聊。
余数齐了再挑目标。把所有数排好序，取正中间那个，也就是中位数，它到各数的绝对距离之和最小。道理是：目标从中位数往任一边挪一小步，那一边的数离目标近一点、另一边远一点，而中位数两侧数目相当，挪动只会让数多一侧涨得比数少一侧减得多，总距离不降反升。所以定它当目标，每个数到它的距离除以 x 就是要动的次数，加起来即答案。
四步走：拍扁、查余数、排序取中位、距离求和
整套流程照参考代码走四步。第一步拍扁，把二维网格一行行读下来接成一维数组，之后只看每个数离目标多远。第二步查余数，拿第一个数除以 x 的余数当基准 mod，扫每个数，谁的余数不等于 mod 就立刻返回 -1。第三步排序，把数组从小到大排好，取下标为长度右移一位那个当中位数，右移一位就是长度除以 2 向下取整。第四步求和，逐个算每个数与中位数的差、取绝对值再除以 x，累加就是最少操作数。
grid=[[2,4],[6,8]]、x=2 这组，4 从哪来
拍扁 grid=[[2,4],[6,8]] 得到 2、4、6、8。查余数：2 除以 2 余 0，当基准 mod；4、6、8 除以 2 都余 0，全部对齐，不返回 -1。
排序后还是 2、4、6、8，长度 4 右移一位得下标 2，取 nums[2]=6 当目标。挨个折算：2 到 6 差 4，除以 2 是 2 次；4 到 6 差 2，除以 2 是 1 次；6 到 6 差 0，不动；8 到 6 差 2，除以 2 是 1 次。加起来 2+1+0+1=4，正是题面给的 4。
复杂度卡在排序，还有几处边界要想清
复杂度上，拍扁、查余数、求距离和各扫一遍是 O(mn)，m 行 n 列共 mn 个数，真正拖后腿的是中间那次排序 O(mn log(mn))，这就是总时间；空间要存拍扁后的一维数组，是 O(mn)。边界也顺带想清：网格只剩一个格子本就相等，答案 0；所有数已全相等，距离和为 0，同样是 0；余数对不齐则数字再规整也返回 -1。偶数个数不必纠结取上取下，取下标长度右移一位那个即可，两个中位数总距离相同。
▶ 动画逐步走查（文字版）——想跟着上方动画一帧帧对照就展开
记牢这套路:第一步查同余定生死,第二步排序取中位数当目标,第三步把每个数到中位数的距离除以 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 · 吴师兄开源图解算法，几十万开发者在看的算法讲解
想成体系刷透这类套路？去图解算法专题