难度: Medium
给你一个大小为 m x n 的二维整数网格 grid 和一个整数 x 。每一次操作，你可以对 grid 中的任一元素 加 x 或 减 x 。
单值网格 是全部元素都相等的网格。
返回使网格化为单值网格所需的 最小 操作数。如果不能，返回 -1 。
示例 1：
输入：grid = [[2,4],[6,8]], x = 2 输出：4 解释：可以执行下述操作使所有元素都等于 4 ： - 2 加 x 一次。 - 6 减 x 一次。 - 8 减 x 两次。 共计 4 次操作。
示例 2：
输入：grid = [[1,5],[2,3]], x = 1 输出：5 解释：可以使所有元素都等于 3 。
示例 3：
输入：grid = [[1,2],[3,4]], x = 2 输出：-1 解释：无法使所有元素相等。
提示：
m == grid.lengthn == grid[i].length1 <= m, n <= 1051 <= m * n <= 1051 <= x, grid[i][j] <= 104运行时间: 164 ms
内存: 37.1 MB
class Solution:
def minOperations(self, grid: List[List[int]], x: int) -> int:
# 中位数贪心吧
dit = defaultdict(int)
m,n = len(grid),len(grid[0])
for i in range(m):
for j in range(n):
dit[grid[i][j]] +=1
nums = []
sumV = 0
for k in dit:
nums.append([k,dit[k]])
sumV+=dit[k]
nums.sort(key=lambda a:a[0])
cur = 0
target = 0
for v,count in nums:
cur += count
if cur* 2>= sumV:
# print("v,count,sumV,cur",v,count,sumV,cur)
target = v
# 到达中位数
break
ans = 0
for v,count in nums:
if (target-v)%x !=0:
return -1
ans += abs(target-v)*(count)//x
return ans
此题解采用中位数为目标值的贪心策略。首先，创建一个字典统计每个元素出现的次数。通过遍历网格，将元素及其出现次数存入字典。然后将字典的内容转换为列表，并按元素值排序。通过遍历排序后的列表，寻找中位数作为目标值，因为中位数最小化了加减操作的总数。之后，对每个元素，计算其与目标值的差值。如果差值不是x的倍数，则返回-1，因为这表明无法通过加减x使所有元素值相等。如果差值是x的倍数，计算将该元素调整到目标值需要的操作数，并累加到总操作数中。
时间复杂度: O(m*n + k*log(k))
空间复杂度: O(k)
class Solution:
def minOperations(self, grid: List[List[int]], x: int) -> int:
# 创建字典统计每个元素的频率
dit = defaultdict(int)
m, n = len(grid), len(grid[0])
for i in range(m):
for j in range(n):
dit[grid[i][j]] += 1
nums = []
sumV = 0
# 将字典转换为列表并计算总元素数量
for k in dit:
nums.append([k, dit[k]])
sumV += dit[k]
nums.sort(key=lambda a: a[0])
cur = 0
target = 0
# 寻找中位数作为目标值
for v, count in nums:
cur += count
if cur * 2 >= sumV:
target = v
break
ans = 0
# 计算所有元素到目标值的总操作次数
for v, count in nums:
if (target - v) % x != 0:
return -1
ans += abs(target - v) * (count) // x
return ans
中位数作为目标值的选择是由于其在数值分布中的位置能够最小化到每个点的距离总和。在需要通过增加或减少固定数值（此处为 x）来统一所有数值的情况下，中位数能够有效地减少总的操作次数。而平均值虽然在一些统计问题中是好的选择，但在需要以整数操作进行调整的问题中，可能不是整数，也可能不是可通过x的整数倍调整达到的值。
如果存在任意两个元素之间的差值不是 x 的整数倍，那么无法通过加减操作使这两个元素相等。因此，如果任何一个元素与目标值之间的差不是 x 的倍数，将所有元素调整为相同值的尝试必然失败。这意味着不可能存在其他的数值作为目标值以满足条件。
将差值除以 x 是为了计算将单个元素调整到目标值需要的基本操作数（即每次操作改变的是 x 单位）。然后乘以该元素出现的次数，是因为每一个相同的元素都需要相同数量的操作来达到目标值。这样的计算逻辑确保了总操作次数反映了使所有元素达到目标值所需的全部操作。
如果网格中所有元素已经相等，那么它们本身就已经是目标值，不需要任何操作。在这种情况下，算法中计算差值的部分结果为零，因此总操作数也是零。所以，如果输入的网格中所有元素一开始就相等，算法会返回 0。