題目資訊

• 題目編號: 2033
• 題目連結: Minimum Operations to Make a Uni-Value Grid
• 主題: Array, Math, Sorting, Matrix

題目敘述

你有一個大小為 $m \times n$ 的二維整數 grid 和一個整數 $x$。在一次操作中，你可以對 grid 中的任何元素加上 $x$ 或減去 $x$。

一個同值網格是一個所有元素都相等的網格。

返回將網格變為同值網格的最小操作次數。如果不可能，返回 -1。

範例 1:

輸入: grid = [[2,4],[6,8]], x = 2
輸出: 4
解釋: 我們可以通過以下操作使每個元素等於4:
- 對2加上一次x。
- 對6減去一次x。
- 對8減去兩次x。
總共使用了4次操作。

範例 2:

輸入: grid = [[1,5],[2,3]], x = 1
輸出: 5
解釋: 我們可以使每個元素等於3。

範例 3:

輸入: grid = [[1,2],[3,4]], x = 2
輸出: -1
解釋: 不可能使每個元素相等。

約束條件:

• $m == \text{grid.length}$
• $n == \text{grid[i].length}$
• $1 \leq m, n \leq 10^5$
• $1 \leq m \times n \leq 10^5$
• $1 \leq x, \text{grid[i][j]} \leq 10^4$

直覺

此問題要求將給定的網格轉換為單值網格，其中所有元素相等，並使用一系列定義的操作。每次操作涉及在網格的一個元素上加或減給定的整數 $x$。最佳的方法是引導元素的轉換朝向集中趨勢，特別是網格值的中位數，從而確保最小的總體距離。

解法

解法開始於將二維網格展平成一維陣列。這一操作簡化了對多維數據的處理，使我們更容易排序和操作網格的值。

1. 展平網格：將二維網格的每個元素提取並儲存到一維陣列 flatGrid 中。這個過程涉及遍歷網格的每一行，並將每個元素附加到 flatGrid 中。

2. 排序展平後的陣列：獲得網格的展平版本後，對 flatGrid 進行排序。排序是關鍵的一步，因為它使得下一步中位數的識別變得可能。

3. 確定目標值：選擇排序後陣列的中位數作為轉換的目標值。中位數是理想的，因為最小化絕對偏差之和可以通過將元素對齊到這個中央值達成。

4. 計算操作：對 flatGrid 中的每個元素，計算其距離目標值（中位數）的絕對差。差異決定了該元素需要多少變化。若某元素需要轉換以達到目標但其差值不能被 $x$ 整除，那麼根據可用的操作，該元素無法達到目標，這時會立即返回 -1。

5. 操作和：對於那些差值能被 $x$ 整除的元素，計算所需操作的數量，方法是將差異除以 $x$，並將此計數累加到 totalOperations 中。

6. 返回結果：如果所有差值都能被 $x$ 整除，最終的 totalOperations 值代表將網格轉化為單值網格所需的最小操作數。否則，若先前識別出有不能整除的差異，則轉換不可行，該函數返回 -1。

此方法利用中位數的屬性和直接的算術操作，有效地在給定的限制條件下實現網格轉換。

程式碼

C++

class Solution {
public:
    int minOperations(vector<vector<int>>& grid, int x) {
        vector<int> flatGrid;
        
        // 將二維網格扁平化為一維陣列以便進行操作
        for (vector<int>& row : grid) {
            for (int value : row) {
                flatGrid.push_back(value);
            }
        }
        
        // 對一維陣列進行排序以找到中位數
        sort(flatGrid.begin(), flatGrid.end());
        
        int totalOperations = 0;
        int targetValue = flatGrid[flatGrid.size() / 2]; 
        
        // 計算將網格變為同值網格所需的總操作數
        for (int i = 0; i < flatGrid.size(); i++) {
            int difference = abs(flatGrid[i] - targetValue);
            
            // 檢查是否可能使所有元素相等
            if (difference % x != 0) {
                return -1;
            }
            
            totalOperations += difference / x;
        }
        
        return totalOperations;
    }
};

Python

class Solution:
    def minOperations(self, grid, x):
        flatGrid = []
        
        # 將二維的 grid 展平成一維的陣列以利於操作
        for row in grid:
            for value in row:
                flatGrid.append(value)
        
        # 將一維陣列排序以找到中位數
        flatGrid.sort()
        
        totalOperations = 0
        targetValue = flatGrid[len(flatGrid) // 2]
        
        # 計算需要多少操作次數才能使 grid 成為單一值的陣列
        for i in range(len(flatGrid)):
            difference = abs(flatGrid[i] - targetValue)
            
            # 檢查是否有可能將所有元素變得相等
            if difference % x != 0:
                return -1
            
            totalOperations += difference // x
        
        return totalOperations

複雜度分析

• 時間複雜度: $O(m \times n \log (m \times n))$

  該解法涉及幾個關鍵步驟：將網格展平成一維陣列，對該陣列進行排序，然後遍歷它以計算總操作次數。

  • 展平成一維陣列的網格需要 $O(m \times n)$ 的時間，因為每個元素都被訪問一次。

  • 對展平後的陣列排序需要 $O(m \times n \log (m \times n))$ 的時間複雜度，在時間上這一步驟占據主導地位。

  • 一旦排序完成，算法計算操作次數，這同樣需要 $O(m \times n)$ 的時間，因為每個元素都被處理一次。

  因此，整體時間複雜度主要受排序步驟支配，達到 $O(m \times n \log (m \times n))$ 的複雜度。

• 空間複雜度: $O(m \times n)$

  • 空間複雜度由所使用的附加空間決定，主要包括用於存儲原始網格元素的 flatGrid 向量。該向量包含 $m \times n$ 個元素。

  • 除此之外，還使用了如 totalOperations 和 targetValue 等變量的常量空間。

  因此，整體空間複雜度為 $O(m \times n)$。