2033. Minimum Operations to Make a Uni-Value Grid

練習日期： 2026-04-28
難度： Medium
類型： Array、Math、Sorting、Matrix

📘 題目敘述

給定一個 m x n 的整數矩陣 grid，以及一個整數 x。

一次操作中，你可以對任意一個元素：

• 加上 x
• 或減去 x

如果一個 grid 裡所有元素都相等，就叫做 uni-value grid。

請回傳最少需要幾次操作，才能把整個 grid 變成 uni-value grid。
如果根本做不到，回傳 -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

🧠 解題思路

我這題的想法是先把整個 grid 攤平成一個一維陣列，然後找一個最適合當目標值的數。

因為每次操作只能加減 x，所以如果兩個數之間的差不是 x 的倍數，那它永遠不可能透過這種操作變成同一個值。
所以我先選一個目標值 goal，然後檢查每個元素和 goal 的差能不能被 x 整除。

而在所有可行的目標值裡，要讓總操作次數最少，最佳選擇會是中位數。
所以我先把所有數字排序，取中間那個值當作 goal。

接著把每個元素變成 goal 所需的操作次數加總起來，就是答案。

所有變數

• m：grid 的列數
• n：grid 的行數
• ans：最後最少操作次數
• goal：最後要把所有元素變成的目標值
• v：把整個 grid 攤平成一維後的陣列

🪜 主要流程步驟

1. 先把整個 grid 攤平成一維陣列

我先把 grid 裡所有元素都放進一個一維陣列 v：

這樣做的目的是把二維問題轉成一維問題，後面比較方便排序和選中位數。

2. 把所有數字排序，選中位數當目標值

接著我把 v 排序：

sort(v.begin(), v.end());

然後取中間那個值當成 goal。

這是因為如果要最小化所有元素到目標值的絕對差總和，最好的選擇就是中位數。
而這題每次操作的成本其實就是差值除以 x，所以本質上仍然是在最小化總差距。

3. 檢查每個元素能不能變成 goal

對每個元素 grid[i][j]，我先算它和 goal 的差距：

int now = abs(grid[i][j] - goal);

如果這個差距不是 x 的倍數：

if (now % x != 0) {
    return -1;
}

那就代表這個元素不可能透過反覆加減 x 變成 goal，
整題就直接無解，回傳 -1。

4. 如果可以變成 goal，就把需要的操作次數加進答案

如果差距 now 可以被 x 整除，
那把這個元素變成 goal 需要的操作次數就是：

now / x

所以我直接累加到 ans：

ans += now / x;

把所有元素的操作次數都加總起來之後，就是最少總操作數。

5. 全部處理完後回傳答案

如果整個 grid 都檢查完，而且每個元素都能變成 goal，
那最後 ans 就是最小操作次數，直接回傳即可。

⏱️ 複雜度

設 N = m * n。

• 時間複雜度：O(N log N)
  先把所有元素攤平，再排序，最後再掃一次計算答案。
• 空間複雜度：O(N)
  我另外用了一個一維陣列 v 來存所有元素。

💻 程式碼實作

class Solution {
public:
    int minOperations(vector<vector<int>>& grid, int x) {
        int m = grid.size();
        int n = grid[0].size();
        int ans = 0;
        int goal;
        vector<int> v;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                v.push_back(grid[i][j]);
            }
        }
        sort(v.begin(), v.end());
        goal = v[(m * n) / 2];
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                int now = abs(grid[i][j] - goal);
                if (now % x != 0) {
                    return -1;
                }
                ans += now / x;
            }
        }
        return ans;
    }
};

🔗 題目連結

https://leetcode.com/problems/minimum-operations-to-make-a-uni-value-grid/