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

发表于 更新于 分类于

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

    给你一个大小为 m x n 的二维整数网格 grid 和一个整数 x 。每一次操作，你可以对 grid 中的任一元素 加 x 或 减 x 。

    单值网格 是全部元素都相等的网格。

    返回使网格化为单值网格所需的 最小 操作数。如果不能，返回 -1 。

    示例 1：

    ```txt

    输入：grid = [[2,4],[6,8]], x = 2

    输出：4

    解释：可以执行下述操作使所有元素都等于 4 ：

    • 2 加 x 一次。

    • 6 减 x 一次。

    • 8 减 x 两次。

    共计 4 次操作。

    ```

    示例 2：

    ```txt

    输入：grid = [[1,5],[2,3]], x = 1

    输出：5

    解释：可以使所有元素都等于 3 。

    ```

    示例 3：

    ```txt

    输入：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

题目

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

给你一个大小为 m x n 的二维整数网格 grid 和一个整数 x 。每一次操作，你可以对 grid 中的任一元素 加 x 或 减 x 。

单值网格 是全部元素都相等的网格。

返回使网格化为单值网格所需的 最小 操作数。如果不能，返回 -1 。

示例 1：

1
2
3
4
5
6
7
输入：grid = [[2,4],[6,8]], x = 2
输出：4
解释：可以执行下述操作使所有元素都等于 4 ： 
- 2 加 x 一次。
- 6 减 x 一次。
- 8 减 x 两次。
共计 4 次操作。

示例 2：

1
2
3
输入：grid = [[1,5],[2,3]], x = 1
输出：5
解释：可以使所有元素都等于 3 。

示例 3：

1
2
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

题解

方法一：

思路

中位数贪心

首先所有的数都应该模x同余，否则没有答案输出-1

然后对数组排序，取中位数作为最终的单值。

为什么中位数，如果最终的单值为t

数组中小于t的个数有a个，大于t的有b个。

让t增大x后，最后需要操作的次数需要增加a-b次。

让t减小x后，最后需要操作的次数需要增加b-a次。

当a=b时总操作次数才最小，也就是应该选择中位数。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public:
    using ll = long long;
    int minOperations(vector<vector<int>>& g, int x) {
        vector<ll> a;
        ll m = g[0][0]%x;
        for (auto& i:g) {
            for (ll j:i) {
                if (j%x != m) return -1;
                a.push_back(j);
            }
        }
        sort(a.begin(), a.end());
        ll n = a.size();
        ll mid = a[n/2];
        ll ans = 0;
        for (ll i:a) {
            ans += abs(i-mid)/x;
        }
        return ans;
    }
};