获取单值网格的最小操作数
难度:
标签:
题目描述
给你一个大小为 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
/*
* 思路：
* 首先将所有元素转化为一个一维数组，然后检查是否可以通过加减x得到单值网格。
* 如果每个元素对x的取余数不同，则返回-1。
* 否则，找到中位数，计算使所有元素变成中位数的操作数。
*/
import java.util.Arrays;
import java.util.stream.IntStream;
public class Solution {
public int minOperations(int[][] grid, int x) {
int m = grid.length;
int n = grid[0].length;
int[] arr = Arrays.stream(grid).flatMapToInt(Arrays::stream).toArray();
Arrays.sort(arr);
int median = arr[arr.length / 2];
int operations = IntStream.of(arr).map(num -> {
int diff = Math.abs(num - median);
if (diff % x != 0) {
return -1;
}
return diff / x;
}).sum();
return operations < 0 ? -1 : operations;
}
}解释
方法:
此题解采用中位数为目标值的贪心策略。首先，创建一个字典统计每个元素出现的次数。通过遍历网格，将元素及其出现次数存入字典。然后将字典的内容转换为列表，并按元素值排序。通过遍历排序后的列表，寻找中位数作为目标值，因为中位数最小化了加减操作的总数。之后，对每个元素，计算其与目标值的差值。如果差值不是x的倍数，则返回-1，因为这表明无法通过加减x使所有元素值相等。如果差值是x的倍数，计算将该元素调整到目标值需要的操作数，并累加到总操作数中。
时间复杂度:
O(m*n + k*log(k))
空间复杂度:
O(k)
代码细节讲解
🦆
为什么选择中位数作为目标值而不是平均值或其他数值？
▷🦆
如果差值不是x的倍数就返回-1，这种情况下是否有可能存在其他数值作为目标值从而使所有元素值通过加减x操作相等？
▷🦆
在计算操作次数时，为什么将差值除以x后再乘以元素出现的次数，这样的计算逻辑是如何确保正确性的？
▷🦆
如何处理网格中所有元素已经相等的情况？在当前的算法实现中，这种情况下的返回值是什么？
▷