Leetcode每日一题 —— 2033. 获取单值网格的最小操作数
- 内容介绍
- 文章标签
- 相关推荐
2033. 获取单值网格的最小操作数 - 力扣（LeetCode）
2033. 获取单值网格的最小操作数 - 给你一个大小为m x n 的二维整数网格 grid 和一个整数 x 。每一次操作，你可以对 grid 中的任一元素 加 x 或 减 x 。 单值网格 是全部元素都相等的网格。 返回使网格化为单值网格所需的 最小 操作数。如果不能，返回 -1 。 示例 1： [https://assets.leetcode.com/uploads/2021/09/21/gridtxt.png] 输入：grid = [[2,4],[6,8]], x =...
思路
- 位置顺序无关，所以可以转换为一维数组排序解答。
排序后结果可用这个表达式表示：
(m-x[1])+(m-x[2])+……+(x[s-2]-m)+(x[s-1]-m) - 选择中位数可以使以上表达式的值最小，而且选择数组中没有的数并不会让结果更优。
代码
class Solution {
public int minOperations(int[][] grid, int x) {
int m = grid.length;
int n = grid[0].length;
int[] nums = new int[m * n];
// 公共的余数
int mod = grid[0][0] % x;
// 将二维数组转为一维数组，方便偏序
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
// 余数不同，说明无法满足条件
if (grid[i][j] % x != mod) {
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;
}
}
PS
另外汇报下为什么一周没答题，因为电脑送修了
其他不说，鸡哥的售后服务还是很不错的，保修后半小时不到就有顺丰小哥上门取件，整体也挺快的。
问了下维修的工程师，原因说是小板短路，难道是因为积灰太多了？
262adc208fc9db2f56a76ca4266c66d1080×3141 203 KB
--【壹】--：
好久没写java了 …
class Solution {
public int minOperations(int[][] grid, int x) {
int n = grid.length * grid[0].length;
int[] nums = new int[n];
int i = 0, sum = 0;
int prev = grid[0][0];
for (int[] arr : grid) {
for (int num : arr) {
nums[i++] = num;
sum += num;
if (num % x != prev % x) {
return -1;
}
prev = num;
}
}
Arrays.sort(nums);
int mid = nums[n / 2];
return Arrays.stream(nums).reduce(0, (a, num) -> a + Math.abs(mid - num) / x);
}
}
--【贰】--：
不懂数学, 看起来是得选存在的数, 我都选了一遍.
class Solution {
public:
int minOperations(vector<vector<int>>& grid, int x) {
auto gcd = [&](this auto&& gcd, int a,int b) -> int {
return b == 0 ? a : gcd(b,a % b);
};
int sum = 0;
int last = grid[0][0];
int d = 0;
int m = grid.size(),n = grid[0].size();
std::vector<int> v(n * m,0);
for(int i = 0; i < m; i++) {
for(int j = 0; j < n; j++) {
const auto val = grid[i][j];
sum += val;
v[i * n + j] = val;
}
}
std::sort(v.begin(),v.end());
for(int i = 0; i + 1 < v.size(); i++) {
d = gcd(d,v[i + 1] - v[i]);
}
if(d % x) {
return -1;
}
int res = 1e9;
int presum = 0;
for(int i = 0; i < v.size(); i++) {
int lp = (i)* v[i],rp = (v.size() - i) * v[i];
int lcount = (lp - presum) / x, rcount = (sum - presum - rp) / x;
res = min(res,lcount + rcount);
presum += v[i];
}
return res;
}
};
--【叁】--：
有问题，如果有负数怎么办，mod不一定相等
--【肆】--：
好消息是haskell里的mod的定义就是数学定义
(x `div` y) * y + (x `mod` y) == x
别的语言大概可以先求模再加上模数再求一次就行了
--【伍】--：
preprocess :: [[Int]] -> UV.Vector Int
preprocess xs = runST $ UV.thaw >=> liftA2 (*>) VA.sort UV.unsafeFreeze $ UV.fromList $ concat xs
minOperations :: [[Int]] -> Int -> Int
minOperations (preprocess -> v) x =
let m = (v UV.! 0) `mod` x
n = UV.length v
in if UV.any ((/= m) . (`mod` x)) v then -1 else let target = v UV.! (n `div` 2) in UV.sum (UV.map (\y -> abs (y - target) `div` x) v)
--【陆】--：
是的，不同语言对模的处理不一样，不过这个题不考这一点
--【柒】--：
Long time no see!lao!
today’s problem is math
class Solution:
def minOperations(self, grid: List[List[int]], x: int) -> int:
m, n = len(grid), len(grid[0])
md = grid[0][0] % x
nums = []
for i in range(m):
for j in range(n):
y = grid[i][j]
if y % x != md:
return -1
nums.append(y)
nums.sort()
mid = m * n >> 1
ans = 0
for i in range(m * n):
ans += abs(nums[mid] - nums[i]) // x
return ans
--【捌】--：
要注意题里写明了范围 1 <= x, grid[i][j] <= 10^4
如果有负数的话就要 (grid[i][j] % x + x) % x != mod
--【玖】--：
一句话 中位数贪心 可以看灵神的题单 分享丨【算法题单】贪心算法（基本贪心策略/反悔/区间/字典序/数学/思维/构造） - 讨论 - 力扣（LeetCode） 4.5
--【拾】--：
欢迎回来！
今天这题的话，首先要加减 x 能达到全网格值相等，首先网格中每个数字除以 x 的余数要一致，否则是不可能的。
如果满足余数一致，就可以把矩阵元素排序成线性序列，然后找到中间位置，让其他所有元素值都靠向中间位置元素值，这样所需的操作数就是最小的。
class Solution {
public:
int minOperations(vector<vector<int>>& grid, int x) {
int m=grid.size(),n=grid[0].size();
// 注意 m*n 最大有 10^5
// 要加减 x 能达到全网格值相等，首先网格中所有数字 / x 的余数要相同
// 如果都相同了，排序取中间值，所有数都往中间值靠
vector<int> seq;
int prevRemainder=grid[0][0] % x;
for(int i=0;i<m;i++){
for(int j=0;j<n;j++){
if(grid[i][j]%x!=prevRemainder){
// 余数不同
return -1;
}
seq.emplace_back(grid[i][j]);
}
}
sort(seq.begin(),seq.end());
int midIdx=(m*n-1)>>1;
int res=0;
for(int i=0;i<seq.size();i++){
if(midIdx>i){
res+=(seq[midIdx]-seq[i])/x;
}else{
res+=(seq[i]-seq[midIdx])/x;
}
}
return res;
}
};
2033. 获取单值网格的最小操作数 - 力扣（LeetCode）
2033. 获取单值网格的最小操作数 - 给你一个大小为m x n 的二维整数网格 grid 和一个整数 x 。每一次操作，你可以对 grid 中的任一元素 加 x 或 减 x 。 单值网格 是全部元素都相等的网格。 返回使网格化为单值网格所需的 最小 操作数。如果不能，返回 -1 。 示例 1： [https://assets.leetcode.com/uploads/2021/09/21/gridtxt.png] 输入：grid = [[2,4],[6,8]], x =...
思路
- 位置顺序无关，所以可以转换为一维数组排序解答。
排序后结果可用这个表达式表示：
(m-x[1])+(m-x[2])+……+(x[s-2]-m)+(x[s-1]-m) - 选择中位数可以使以上表达式的值最小，而且选择数组中没有的数并不会让结果更优。
代码
class Solution {
public int minOperations(int[][] grid, int x) {
int m = grid.length;
int n = grid[0].length;
int[] nums = new int[m * n];
// 公共的余数
int mod = grid[0][0] % x;
// 将二维数组转为一维数组，方便偏序
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
// 余数不同，说明无法满足条件
if (grid[i][j] % x != mod) {
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;
}
}
PS
另外汇报下为什么一周没答题，因为电脑送修了
其他不说，鸡哥的售后服务还是很不错的，保修后半小时不到就有顺丰小哥上门取件，整体也挺快的。
问了下维修的工程师，原因说是小板短路，难道是因为积灰太多了？
262adc208fc9db2f56a76ca4266c66d1080×3141 203 KB
--【壹】--：
好久没写java了 …
class Solution {
public int minOperations(int[][] grid, int x) {
int n = grid.length * grid[0].length;
int[] nums = new int[n];
int i = 0, sum = 0;
int prev = grid[0][0];
for (int[] arr : grid) {
for (int num : arr) {
nums[i++] = num;
sum += num;
if (num % x != prev % x) {
return -1;
}
prev = num;
}
}
Arrays.sort(nums);
int mid = nums[n / 2];
return Arrays.stream(nums).reduce(0, (a, num) -> a + Math.abs(mid - num) / x);
}
}
--【贰】--：
不懂数学, 看起来是得选存在的数, 我都选了一遍.
class Solution {
public:
int minOperations(vector<vector<int>>& grid, int x) {
auto gcd = [&](this auto&& gcd, int a,int b) -> int {
return b == 0 ? a : gcd(b,a % b);
};
int sum = 0;
int last = grid[0][0];
int d = 0;
int m = grid.size(),n = grid[0].size();
std::vector<int> v(n * m,0);
for(int i = 0; i < m; i++) {
for(int j = 0; j < n; j++) {
const auto val = grid[i][j];
sum += val;
v[i * n + j] = val;
}
}
std::sort(v.begin(),v.end());
for(int i = 0; i + 1 < v.size(); i++) {
d = gcd(d,v[i + 1] - v[i]);
}
if(d % x) {
return -1;
}
int res = 1e9;
int presum = 0;
for(int i = 0; i < v.size(); i++) {
int lp = (i)* v[i],rp = (v.size() - i) * v[i];
int lcount = (lp - presum) / x, rcount = (sum - presum - rp) / x;
res = min(res,lcount + rcount);
presum += v[i];
}
return res;
}
};
--【叁】--：
有问题，如果有负数怎么办，mod不一定相等
--【肆】--：
好消息是haskell里的mod的定义就是数学定义
(x `div` y) * y + (x `mod` y) == x
别的语言大概可以先求模再加上模数再求一次就行了
--【伍】--：
preprocess :: [[Int]] -> UV.Vector Int
preprocess xs = runST $ UV.thaw >=> liftA2 (*>) VA.sort UV.unsafeFreeze $ UV.fromList $ concat xs
minOperations :: [[Int]] -> Int -> Int
minOperations (preprocess -> v) x =
let m = (v UV.! 0) `mod` x
n = UV.length v
in if UV.any ((/= m) . (`mod` x)) v then -1 else let target = v UV.! (n `div` 2) in UV.sum (UV.map (\y -> abs (y - target) `div` x) v)
--【陆】--：
是的，不同语言对模的处理不一样，不过这个题不考这一点
--【柒】--：
Long time no see!lao!
today’s problem is math
class Solution:
def minOperations(self, grid: List[List[int]], x: int) -> int:
m, n = len(grid), len(grid[0])
md = grid[0][0] % x
nums = []
for i in range(m):
for j in range(n):
y = grid[i][j]
if y % x != md:
return -1
nums.append(y)
nums.sort()
mid = m * n >> 1
ans = 0
for i in range(m * n):
ans += abs(nums[mid] - nums[i]) // x
return ans
--【捌】--：
要注意题里写明了范围 1 <= x, grid[i][j] <= 10^4
如果有负数的话就要 (grid[i][j] % x + x) % x != mod
--【玖】--：
一句话 中位数贪心 可以看灵神的题单 分享丨【算法题单】贪心算法（基本贪心策略/反悔/区间/字典序/数学/思维/构造） - 讨论 - 力扣（LeetCode） 4.5
--【拾】--：
欢迎回来！
今天这题的话，首先要加减 x 能达到全网格值相等，首先网格中每个数字除以 x 的余数要一致，否则是不可能的。
如果满足余数一致，就可以把矩阵元素排序成线性序列，然后找到中间位置，让其他所有元素值都靠向中间位置元素值，这样所需的操作数就是最小的。
class Solution {
public:
int minOperations(vector<vector<int>>& grid, int x) {
int m=grid.size(),n=grid[0].size();
// 注意 m*n 最大有 10^5
// 要加减 x 能达到全网格值相等，首先网格中所有数字 / x 的余数要相同
// 如果都相同了，排序取中间值，所有数都往中间值靠
vector<int> seq;
int prevRemainder=grid[0][0] % x;
for(int i=0;i<m;i++){
for(int j=0;j<n;j++){
if(grid[i][j]%x!=prevRemainder){
// 余数不同
return -1;
}
seq.emplace_back(grid[i][j]);
}
}
sort(seq.begin(),seq.end());
int midIdx=(m*n-1)>>1;
int res=0;
for(int i=0;i<seq.size();i++){
if(midIdx>i){
res+=(seq[midIdx]-seq[i])/x;
}else{
res+=(seq[i]-seq[midIdx])/x;
}
}
return res;
}
};