2021.10.10 buckle - minimum operation to obtain a single value grid

It's too powerful 2022-01-15 01:46:00

The second question of this week's competition , Refer to the big man's solution : Power button

Title Description :

Give you a size of  m x n Two dimensional integer grid grid And an integer x . Every operation , You can be right grid Any element of Add x or reduce x .

Single value grid Is a grid where all elements are equal .

Returns the required to turn the grid into a single valued grid Minimum Operands . If not , return -1 .

Method 1 :

class Solution {
public:
int minOperations(vector<vector<int>>& grid, int x) {
int m = grid.size();
int n = grid[0].size();
vector<int> cur;
for (int i = 0; i < m; i++)
{
for (int j = 0; j < n; j++)
{
if ((grid[i][j] - grid[0][0]) % x == 0) // Take any number as the benchmark ,
// If the difference between other elements and this number is x Multiple , So it's easy to get that the difference between any two numbers is x Multiple
cur.push_back(grid[i][j]);
else return -1;
}
}
sort(cur.begin(), cur.end());
int mid = cur[m * n / 2]; // Median , If the number of elements is even , Then the middle two numbers can
int count = 0;
for (int num : cur)
{
count += abs(num - mid) / x;
}
return count;
}
};

A problem that requires some mathematical thinking and finding rules , The question can be summed up in four words :“ Find the median ”.


thank
Similar articles
***

2022-01-15

***

2022-01-15

***

2022-01-15

2022-01-15

2022-01-15

2022-01-15

2022-01-15

2022-01-15