leetcode 2033. 获取单值网格的最小操作数 题解（两个重要知识点，取中位数好理解一点）
这道题有两个知识点个人认为比较重要。
第一个：
要使任意两元素最终相等，这两元素的差必须是 x 的倍数，否则无法通过加减 x 来相等
亦即：要使两个元素通过加减x来变成相等，它们之间的差一定是x的倍数吗？？？也就是说上面这个知识点是充要条件吗？
证明：
这个证明比较简单。
假设有两个整数a，b和x。要使得a+a′x=b+b′xb−a=a′x−b′x有b−a=(a′−b′)x。易知a′,b′和x都是整数，所以是成立的假设有两个整数a，b和x。\\ 要使得a + a'x = b + b'x \\ b - a = a'x - b'x \\ 有b - a = (a'-b')x。 易知a',b'和x都是整数，所以是成立的假设有两个整数a，b和x。要使得a+a′x=b+b′xb−a=a′x−b′x有b−a=(a′−b′)x。易知a′,b′和x都是整数，所以是成立的
结合一下同余定理可知要令最后各个数通过加减x来最终相等，那么可以：
我们可以以数组中的某一元素为基准，若所有元素与它的差均为 x 的倍数，则任意两元素之差为 x 的倍数
第二个：
参考这一个题解：[java]贪心 取中位数（垃圾解释） - 获取单值网格的最小操作数 - 力扣（LeetCode） (leetcode-cn.com)
图来源于[java]贪心 取中位数（垃圾解释） - 获取单值网格的最小操作数 - 力扣（LeetCode） (leetcode-cn.com)
这个问题的证明有点像初中数学：求一个点，到直线上的各个点之间的距离之和最小。
具体证明省略。。。
可参考大神的证明：贪心取中位数的理由 - 获取单值网格的最小操作数 - 力扣（LeetCode） (leetcode-cn.com)
结合上面的两个知识点可知：中位数和中位数之间的所有整数到各个点之间的距离之和最小。但是，数组中的数不一定能通过加减x最终变成，比如输入数组[2,4,6,8]，x=2。虽然5也是到各个点之和最小，但是数组中的数并不能通过加减x变成5。因此我们直接取中位数就好了。
只要数组中的每个数与数组中的某个数的差是x的倍数， 那么每一个数都能通过加减x变成中位数
中位数解法：
public int minOperations(int[][] grid, int x) { int[] nums = new int[grid.length * grid[0].length]; int max = Integer.MIN_VALUE; int min = Integer.MAX_VALUE; int idx = 0; // 校验 for (int i = 0; i < grid.length; i++) { for (int j = 0; j < grid[0].length; j++) { nums[idx++] = grid[i][j]; max = Math.max(grid[i][j], max); min = Math.min(grid[i][j], min); if ((grid[i][j] - grid[0][0]) % x != 0) { return -1; } } } // 先排序 Arrays.sort(nums); int mid = nums[nums.length / 2]; int result = 0; for (int i = 0; i < nums.length; i++) { result += Math.abs((mid - nums[i]) / x); } return result; } 复制代码前缀和解法:
public int minOperations(int[][] grid, int x) { int[] nums = new int[grid.length * grid[0].length]; int max = Integer.MIN_VALUE; int min = Integer.MAX_VALUE; int idx = 0; for (int i = 0; i < grid.length; i++) { for (int j = 0; j < grid[0].length; j++) { nums[idx++] = grid[i][j]; max = Math.max(grid[i][j], max); min = Math.min(grid[i][j], min); if ((grid[i][j] - grid[0][0]) % x != 0) { return -1; } } } // 先排序，在求前缀和 Arrays.sort(nums); int[] prefixSum = new int[grid.length * grid[0].length + 1]; for (int i = 1; i < prefixSum.length; i++) { prefixSum[i] = prefixSum[i - 1] + nums[i - 1]; } int result = Integer.MAX_VALUE; for (int i = 0; i < nums.length; i++) { // 左边 int deltaLeftSum = (i + 1) * nums[i] - (prefixSum[i + 1] - prefixSum[0]); // 右边 int deltaRightSum = (prefixSum[nums.length] - prefixSum[i + 1]) - (nums.length - i - 1) * nums[i]; result = Math.min(result, (deltaRightSum + deltaLeftSum) / x); } return result; }
作者：壁咚王我当定了
链接：https://juejin.cn/post/7018171309116882951