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

把整张网格变成同一个数，最少动几次

给一个 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。偶数个数不必纠结取上取下，取下标长度右移一位那个即可，两个中位数总距离相同。

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

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 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;
    }
};

Java

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;
    }
}