README.md

2033. 获取单值网格的最小操作数

English Version

题目描述

给你一个大小为 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.length
• n == grid[i].length
• 1 <= m, n <= 105
• 1 <= m * n <= 105
• 1 <= x, grid[i][j] <= 104

解法

Python3

class Solution:
    def minOperations(self, grid: List[List[int]], x: int) -> int:
        nums = []
        m, n = len(grid), len(grid[0])
        base = grid[0][0]
        for i in range(m):
            for j in range(n):
                if abs(grid[i][j] - base) % x != 0:
                    return -1
                nums.append(grid[i][j])
        nums.sort()
        mid = nums[len(nums) >> 1]
        ans = 0
        for num in nums:
            ans += abs(num - mid) // x
        return ans

Java

class Solution {
    public int minOperations(int[][] grid, int x) {
        int m = grid.length, n = grid[0].length;
        int[] nums = new int[m * n];
        int base = grid[0][0];
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                if (Math.abs(base - grid[i][j]) % x != 0) {
                    return -1;
                }
                nums[i * n + j] = grid[i][j];
            }
        }
        Arrays.sort(nums);
        int mid = nums[nums.length >> 1];
        int ans = 0;
        for (int num : nums) {
            ans += (Math.abs(num - mid) / x);
        }
        return ans;
    }
}

C++

class Solution {
public:
    int minOperations(vector<vector<int>>& grid, int x) {
        vector<int> nums;
        int m = grid.size(), n = grid[0].size();
        int base = grid[0][0];
        for (int i = 0; i < m; ++i)
        {
            for (int j = 0; j < n; ++j)
            {
                if (abs(grid[i][j] - base) % x != 0) return -1;
                nums.push_back(grid[i][j]);
            }
        }
        sort(nums.begin(), nums.end());
        int mid = nums[nums.size() >> 1];
        int ans = 0;
        for (int num : nums) ans += abs(num - mid) / x;
        return ans;
    }
};

Go

func minOperations(grid [][]int, x int) int {
	var nums []int
	m, n, base := len(grid), len(grid[0]), grid[0][0]
	for i := 0; i < m; i++ {
		for j := 0; j < n; j++ {
			if abs(grid[i][j]-base)%x != 0 {
				return -1
			}
			nums = append(nums, grid[i][j])
		}
	}
	sort.Ints(nums)
	mid := nums[len(nums)>>1]
	ans := 0
	for _, num := range nums {
		ans += abs(num-mid) / x
	}
	return ans
}

func abs(x int) int {
	if x > 0 {
		return x
	}
	return -x
}

...