Medium

题目描述

给你一个大小为 m x n 的二维整数网格 grid 和一个整数 x。在一次操作中，你可以对网格的任何元素加上 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.length
  • n == grid[i].length
  • 1 <= m, n <= 10^5
  • 1 <= m * n <= 10^5
  • 1 <= x, grid[i][j] <= 10^4

解题思路

这道题的核心思路基于以下几个关键观察：

  1. 可行性判断：如果两个数 a 和 b 对 x 的余数不同，那么无论进行多少次加减 x 的操作，它们永远不可能相等。因此，网格中所有元素对 x 的余数必须相同，否则返回 -1。

  2. 目标值选择：一旦确定可行，需要选择一个目标值使得总操作数最少。由于每个元素都需要变成这个目标值，而操作次数等于 |原值 - 目标值| / x，这实际上是一个经典的"最小化到某点距离和"问题。

  3. 中位数性质：要使所有点到某个点的距离和最小，该点应该是中位数。将所有元素按值排序后，选择中位数作为目标值能保证操作数最少。

  4. 操作数计算：对于每个元素，操作次数为 abs(element - median) / x，将所有操作次数相加即为答案。

算法步骤：

  • 将二维网格展开为一维数组
  • 检查所有元素模 x 的余数是否相同
  • 对数组排序，选择中位数作为目标值
  • 计算所有元素变为目标值所需的操作数

代码实现

class Solution {
public:
    int minOperations(vector<vector<int>>& grid, int x) {
        vector<int> nums;
        
        // 将二维网格展开为一维数组
        for (auto& row : grid) {
            for (int num : row) {
                nums.push_back(num);
            }
        }
        
        // 检查所有元素模x的余数是否相同
        int remainder = nums[0] % x;
        for (int num : nums) {
            if (num % x != remainder) {
                return -1;
            }
        }
        
        // 排序并找到中位数
        sort(nums.begin(), nums.end());
        int median = nums[nums.size() / 2];
        
        // 计算总操作数
        int operations = 0;
        for (int num : nums) {
            operations += abs(num - median) / x;
        }
        
        return operations;
    }
};

class Solution:
    def minOperations(self, grid: List[List[int]], x: int) -> int:
        # 将二维网格展开为一维数组
        nums = []
        for row in grid:
            for num in row:
                nums.append(num)
        
        # 检查所有元素模x的余数是否相同
        remainder = nums[0] % x
        for num in nums:
            if num % x != remainder:
                return -1
        
        # 排序并找到中位数
        nums.sort()
        median = nums[len(nums) // 2]
        
        # 计算总操作数
        operations = 0
        for num in nums:
            operations += abs(num - median) // x
        
        return operations

public class Solution {
    public int MinOperations(int[][] grid, int x) {
        List<int> nums = new List<int>();
        
        // 将二维网格展开为一维数组
        foreach (var row in grid) {
            foreach (int num in row) {
                nums.Add(num);
            }
        }
        
        // 检查所有元素模x的余数是否相同
        int remainder = nums[0] % x;
        foreach (int num in nums) {
            if (num % x != remainder) {
                return -1;
            }
        }
        
        // 排序并找到中位数
        nums.Sort();
        int median = nums[nums.Count / 2];
        
        // 计算总操作数
        int operations = 0;
        foreach (int num in nums) {
            operations += Math.Abs(num - median) / x;
        }
        
        return operations;
    }
}

var minOperations = function(grid, x) {
    const nums = [];
    
    // 将二维网格展开为一维数组
    for (const row of grid) {
        for (const num of row) {
            nums.push(num);
        }
    }
    
    // 检查所有元素模x的余数是否相同
    const remainder = nums[0] % x;
    for (const num of nums) {
        if (num % x !== remainder) {
            return -1;
        }
    }
    
    // 排序并找到中位数
    nums.sort((a, b) => a - b);
    const median = nums[Math.floor(nums.length / 2)];
    
    // 计算总操作数
    let operations = 0;
    for (const num of nums) {
        operations += Math.abs(num - median) / x;
    }
    
    return operations;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度说明
时间复杂度O(mn log(mn))主要消耗在排序步骤，其中 m×n 是网格中元素的总数
空间复杂度O(mn)需要额外数组存储所有网格元素

相关题目