获取单值网格的最小操作数 图解题解

这道题到底在问什么

输入

grid=[[2,4],[6,8]], x=2

输出

4

输入

grid=[[1,2],[3,4]], x=2

输出

-1(1、3 是奇数,2、4 是偶数,除 2 余数不同)

先想最直接的笨办法

取正中间那个数当目标。9 个数,下标从 0 到 8,中间是下标 4,值是 6。参考代码里就写成 nums 长度右移一位,也就是 9 除以 2 取整等于 4。把 6 定为大家要一起走到的目标值。下面挨个算,每个数走到 6 要几步。（动画第 17 步）

最优解：一步一步想明白

1. 3记牢这套路:第一步查同余定生死,第二步排序取中位数当目标,第三步把每个数到中位数的距离除以 x 累加。下面从拍扁网格开始。
2. 4要把 9 个格子变成同一个值这就是我们的输入,一张 3 行 3 列的网格,右上角记着 x 等于 2。每次操作能给任意一个格子加 2 或减 2。你先扫一眼这 9 个数,全是偶数。接下来第一件事,是把这张二维网格拍扁成一条一维的数,处理起来更顺手。
3. 5把网格一行一行读下来,拉成一条一维数组:8、2、6、4、10、8、6、4、2,一共 9 个数。位置怎么排其实无所谓,因为最后只关心它们各自离目标有多远。拍扁之后,先别急着算,得先回答一个生死问题:这些数到底能不能凑到同一个值上。
4. 6从第 0 个数 8 开始。参考代码拿它除以 x 的余数当作基准:8 除以 2 余 0,于是把 mod 定成 0。之后每一个数都要拿来和这个 0 对比,只要有一个余数不是 0,整张网格就没救了。
5. 7轮到第 1 个数 2,除以 2 余 0,正好等于基准 mod 的 0,过关。它和 8 之间相差的是 2 的整数倍,理论上能靠若干次加减 2 走到一块去。绿色表示这个数已经通过同余检查。
6. 8轮到第 2 个数 6,除以 2 余 0,正好等于基准 mod 的 0,过关。它和 8 之间相差的是 2 的整数倍,理论上能靠若干次加减 2 走到一块去。绿色表示这个数已经通过同余检查。
7. 9轮到第 3 个数 4,除以 2 余 0,正好等于基准 mod 的 0,过关。它和 8 之间相差的是 2 的整数倍,理论上能靠若干次加减 2 走到一块去。绿色表示这个数已经通过同余检查。
8. 10轮到第 4 个数 10,除以 2 余 0,正好等于基准 mod 的 0,过关。它和 8 之间相差的是 2 的整数倍,理论上能靠若干次加减 2 走到一块去。绿色表示这个数已经通过同余检查。
9. 11轮到第 5 个数 8,除以 2 余 0,正好等于基准 mod 的 0,过关。它和 8 之间相差的是 2 的整数倍,理论上能靠若干次加减 2 走到一块去。绿色表示这个数已经通过同余检查。
10. 12轮到第 6 个数 6,除以 2 余 0,正好等于基准 mod 的 0,过关。它和 8 之间相差的是 2 的整数倍,理论上能靠若干次加减 2 走到一块去。绿色表示这个数已经通过同余检查。
11. 13轮到第 7 个数 4,除以 2 余 0,正好等于基准 mod 的 0,过关。它和 8 之间相差的是 2 的整数倍,理论上能靠若干次加减 2 走到一块去。绿色表示这个数已经通过同余检查。
12. 14轮到第 8 个数 2,除以 2 余 0,正好等于基准 mod 的 0,过关。它和 8 之间相差的是 2 的整数倍,理论上能靠若干次加减 2 走到一块去。绿色表示这个数已经通过同余检查。
13. 159 个数全部检查完,除以 2 的余数清一色是 0,同余成立,这张网格一定能变成单值,不用返回 -1。生死关过了,接下来才是正题:选一个共同目标,让总操作数最少。
14. 16把这 9 个数从小到大排好,变成 2、2、4、4、6、6、8、8、10。排序是为了下一步好取中位数。你可能会问,为什么不直接取平均值当目标,先按住这个疑问,等会儿有一帧专门算给你看,平均值反而更亏。
15. 17取正中间那个数当目标。9 个数,下标从 0 到 8,中间是下标 4,值是 6。参考代码里就写成 nums 长度右移一位,也就是 9 除以 2 取整等于 4。把 6 定为大家要一起走到的目标值。下面挨个算,每个数走到 6 要几步。
16. 18看下标 0 这个数 2。它和目标 6 相差 4,而每次操作动 2,所以 要加 2 次 2,折合 2 次操作。把 2 加进累计,现在 ops 等于 2。蓝色的都是已经结算过的数。
17. 19看下标 1 这个数 2。它和目标 6 相差 4,而每次操作动 2,所以 要加 2 次 2,折合 2 次操作。把 2 加进累计,现在 ops 等于 4。蓝色的都是已经结算过的数。
18. 20看下标 2 这个数 4。它和目标 6 相差 2,而每次操作动 2,所以 要加 1 次 2,折合 1 次操作。把 1 加进累计,现在 ops 等于 5。蓝色的都是已经结算过的数。
19. 21看下标 3 这个数 4。它和目标 6 相差 2,而每次操作动 2,所以 要加 1 次 2,折合 1 次操作。把 1 加进累计,现在 ops 等于 6。蓝色的都是已经结算过的数。
20. 22看下标 4 这个数 6。它和目标 6 相差 0,而每次操作动 2,所以 本身就是 6,不用动,折合 0 次操作。把 0 加进累计,现在 ops 等于 6。蓝色的都是已经结算过的数。
21. 23看下标 5 这个数 6。它和目标 6 相差 0,而每次操作动 2,所以 本身就是 6,不用动,折合 0 次操作。把 0 加进累计,现在 ops 等于 6。蓝色的都是已经结算过的数。
22. 24看下标 6 这个数 8。它和目标 6 相差 2,而每次操作动 2,所以 要减 1 次 2,折合 1 次操作。把 1 加进累计,现在 ops 等于 7。蓝色的都是已经结算过的数。
23. 25看下标 7 这个数 8。它和目标 6 相差 2,而每次操作动 2,所以 要减 1 次 2,折合 1 次操作。把 1 加进累计,现在 ops 等于 8。蓝色的都是已经结算过的数。
24. 26看下标 8 这个数 10。它和目标 6 相差 4,而每次操作动 2,所以 要减 2 次 2,折合 2 次操作。把 2 加进累计,现在 ops 等于 10。蓝色的都是已经结算过的数。
25. 279 个数全部结算完,把它们各自走到 6 需要的次数加起来,一共是 10。这就是把整张网格变成单值网格的最少操作数。回头看整条链路:先判同余保证有解,再排序取中位数当目标,最后把每个数的距离折算成次数求和,答案 10。

⚠️ 容易写错的地方

完整代码（Python / C++ / Java）

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 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)

#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 minOperations(vector<vector<int>>& grid, int x) {
        int m = grid.size(), n = grid[0].size();
        int mod = grid[0][0] % x;
        int nums[m * n];
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                if (grid[i][j] % x != mod) {
                    return -1;
                }
                nums[i * n + j] = grid[i][j];
            }
        }
        sort(nums, nums + m * n);
        int mid = nums[(m * n) >> 1];
        int ans = 0;
        for (int v : nums) {
            ans += abs(v - mid) / x;
        }
        return ans;
    }
};

import java.util.*;
class Solution {
    public int minOperations(int[][] grid, int x) {
        int m = grid.length, n = grid[0].length;
        int[] nums = new int[m * n];
        int mod = grid[0][0] % x;
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                if (grid[i][j] % x != mod) {
                    return -1;
                }
                nums[i * n + j] = grid[i][j];
            }
        }
        Arrays.sort(nums);
        int mid = nums[nums.length >> 1];
        int ans = 0;
        for (int v : nums) {
            ans += Math.abs(v - mid) / x;
        }
        return ans;
    }
}

复杂度

面试官可能追问