目录

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

Shen 收录于每日一题

2021-10-18 约 337 字预计阅读 1 分钟

目录

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

中位数

什么情况下，所有的数都可以通过加减x变为同一个数。可以选择第一个数作为base，其他所有的数与base的差值都是x的倍数，那么这些数就可以通过变换变为同一个数
1. [base, base+x, base+2x, base+3x]
如果这些数字都可以变为同一个数，那么哪一个数字y是最佳的数字呢。
1. 需要找的是min(|x1 - y| + |x2 - y| + |x3 - y| ... + |xn - y|)
2. 那么y就是中位数距离所有的点都是最近的点。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38


// #define DEBUG
class Solution {
public:
    int minOperations(vector<vector<int>>& grid, int x) {
        int n = grid.size(), m = grid[0].size();

        vector<int> f;
        int base = grid[0][0];

        for(auto& g: grid) {
            for(auto& c: g) {
                if((c - base) % x != 0) {
                    return -1;
                }        
                f.push_back(c);
            }
        }

        sort(f.begin(), f.end());
        int ans = 0;
#ifdef DEBUG
        printv(f);
        cout << f[m * n / 2] << endl;
#endif
        for(int i = 0; i < f.size(); i++) {
            ans += abs(f[m * n / 2] - f[i]) / x;
        }

        return ans;
    }

    void printv(vector<int>& v) {
        for(int i = 0; i < v.size(); i++) {
            cout << v[i] << ' ';
        }
        cout << endl;
    }
};