LeetCode 2033. 获取单值网格的最小操作数(贪心)

简介: LeetCode 2033. 获取单值网格的最小操作数(贪心)

文章目录


1. 题目

2. 解题


1. 题目


给你一个大小为 m x n 的二维整数网格 grid 和一个整数 x 。

每一次操作,你可以对 grid 中的任一元素 加 x 或 减 x 。


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


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


image.pngimage.png

image.png

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

image.png

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

image.png

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


2. 解题

  • 每个数之间的差必须能被 x 整除
  • 选择中位数作为最终的目标能使次数最少
class Solution {
public:
    int minOperations(vector<vector<int>>& grid, int x) {
        int m = grid.size(), n = grid[0].size(), k = 0, a = grid[0][0];
        vector<int> nums(m*n);
        for(int i = 0; i < m; ++i)
        {
            for(int j = 0; j < n; ++j)
            {
                nums[k++] = grid[i][j];
                if((grid[i][j]-a)%x != 0)
                    return -1;
            }
        }
        sort(nums.begin(), nums.end());
        int target = nums[m*n/2], ct = 0;
        for(auto n : nums)
            ct += abs(n-target)/x;
        return ct;
    }

252 ms 76.4 MB C++

相关文章
|
7月前
|
算法 测试技术 C++
【动态规划】【广度优先搜索】LeetCode:2617 网格图中最少访问的格子数
【动态规划】【广度优先搜索】LeetCode:2617 网格图中最少访问的格子数
Leetcode.965 单值二叉树
Leetcode.965 单值二叉树
28 0
LeetCode | 965. 单值二叉树
LeetCode | 965. 单值二叉树
(leetcode)单值二叉树
(leetcode)单值二叉树
53 0
|
7月前
LeetCode——965. 单值二叉树
LeetCode——965. 单值二叉树
|
7月前
[LeetCode]——965——单值二叉树
[LeetCode]——965——单值二叉树
|
7月前
|
算法 DataX
二叉树(中)+Leetcode每日一题——“数据结构与算法”“剑指Offer55-I. 二叉树的深度”“100.相同的树”“965.单值二叉树”
二叉树(中)+Leetcode每日一题——“数据结构与算法”“剑指Offer55-I. 二叉树的深度”“100.相同的树”“965.单值二叉树”
|
存储 机器学习/深度学习
LeetCode-1001 网格照明
LeetCode-1001 网格照明
|
7月前
leetcode-6110:网格图中递增路径的数目
leetcode-6110:网格图中递增路径的数目
54 1
|
7月前
|
算法 测试技术 C#
【动态规划】【广度优先搜索】LeetCode:2617 网格图中最少访问的格子数
【动态规划】【广度优先搜索】LeetCode:2617 网格图中最少访问的格子数