題目資訊

• 題目編號: 2965
• 題目連結: Find Missing and Repeated Values
• 主題: Array, Hash Table, Math, Matrix

題目敘述

你擁有一個0-索引的二維整數矩陣 grid，其大小為 $n \times n$，且值的範圍在 $[1, n^2]$ 之間。每個整數出現恰好一次，除了 a 出現了兩次，以及 b 是缺失的。任務是找出重複和缺失的數字 a 和 b。

返回一個0-索引整數陣列 ans，大小為 $2$，其中 ans[0] 等於 a，ans[1] 等於 b。

範例 1:

輸入: grid = [[1,3],[2,2]]
輸出: [2,4]
解釋: 數字 2 重複出現，數字 4 缺失，因此答案是 [2,4]。

範例 2:

輸入: grid = [[9,1,7],[8,9,2],[3,4,6]]
輸出: [9,5]
解釋: 數字 9 重複出現，數字 5 缺失，因此答案是 [9,5]。

約束條件:

• $2 \leq n == \text{grid.length} == \text{grid}[i].\text{length} \leq 50$
• $1 \leq \text{grid}[i][j] \leq n \times n$
• 對於所有 $x$，其滿足 $1 \leq x \leq n \times n$ 的條件下，恰好有一個 $x$ 不等於任何 grid 成員。
• 對於所有 $x$，其滿足 $1 \leq x \leq n \times n$ 的條件下，恰好有一個 $x$ 等於 grid 成員中的兩個。
• 對於所有 $x$，其滿足 $1 \leq x \leq n \times n$ 的條件下，除了其中兩個，恰好有一對 $i, j$，滿足 $0 \leq i, j \leq n - 1$ 且 $\text{grid}[i][j] == x$。

直覺

問題描述了一個情境：我們有一個填滿整數的平方矩陣，整數的範圍介於 1 到 $n^2$ 之間。在這個矩陣中，除了某一個整數出現了兩次和另外一個整數完全沒有出現之外，所有的整數恰好出現一次。我們的目標是找到重複出現的整數（記作 a）和缺失的整數（記作 b）。基於這些限制條件，這個問題可以有效地透過利用計數機制來解決，藉由遍歷矩陣來追蹤遇到的數字。通過這樣的方式，我們不僅可以檢測到重複的數字，還可以藉由遺漏來確定哪個數字缺失。

解法

此方法涉及簡單的遍歷和檢查機制：

1. 初始化:

   • 開始時，宣告一個整數 repeated_num 用來存儲一旦被檢測到的重複的數字。
   • 確定矩陣的大小 len，這同時反映了矩陣的維度，因為它是正方形的（即 $n \times n$）。

2. 追蹤出現次數:

   • 使用一個長度為 $n^2 + 1$ 的布林向量 used，並初始化為 false，用來追蹤數字出現過的狀況。這個向量就像是從 1 到 $n^2$ 的數字的雜湊映射。

3. 遍歷矩陣:

   • 遍歷矩陣中的每一個元素。對於每一個數字 num，檢查它是否已經在 used 中被標記為 true：
     • 如果 num 先前已經被遭遇過（即 used[num] 為 true），那麼這個數字即是重複的數字。將它賦值給 repeated_num。
     • 否則，將此 num 在 used 陣列中標記為 true，表示它已經被看到。

4. 識別缺失的數字:

   • 在處理完整個矩陣之後，從 1 到 $n^2$ 遍歷 used 向量。used[i] 保持 false 的索引 i 表示缺失的數字，因為它從未在矩陣中被遇到。

5. 返回結果:

   • 一旦找到重複和缺失的數字，將它們依照順序 $[a, b]$ 返回作為一個向量。

這個結構化的方法保證我們能夠在單次遍歷矩陣之後有效地找到重複和缺失的數字，接著簡單掃描找到缺失的數字。使用布林陣列至關重要，因為這允許在常數時間內進行檢查和標記操作，這對於遵循性能約束是至關重要的。

程式碼

C++

class Solution {
public:
    vector<int> findMissingAndRepeatedValues(vector<vector<int>>& grid) {
        // 'repeated_num'將會儲存重複出現的數值。
        int repeated_num;
        int len = grid.size(); // 'len'是網格的大小，因為它是正方形矩陣。
        
        // 'used'是一個用來追蹤已經遇到的數字的向量。
        vector<bool> used(len * len + 1, false);
        
        // 遍歷2D網格中的每個元素。
        for (vector<int>& row : grid) {
            for (int num : row) {
                // 檢查該數字是否已經出現過；如果是，將其賦值給'repeated_num'。
                if (used[num]) {
                    repeated_num = num;
                }
                used[num] = true; // 將該數字標記為已遇到。
            }
        }
        
        // 透過檢查'used'向量來找到缺少的數字。
        for (int i = 1; i < len * len + 1; i++) {
            if (!used[i]) {
                return {repeated_num, i};
            }
        }
        
        // 如果邏輯失敗，則返回預設值；不過根據約束這不應該發生。
        return {-1, -1};
    }
};

Python

class Solution:
    def findMissingAndRepeatedValues(self, grid):
        # 'repeated_num' 將儲存出現兩次的數值。
        repeated_num = None
        len_grid = len(grid)  # 'len' 是矩陣的大小，因為這是方形矩陣。
        
        # 'used' 是一個列表，用於追蹤已遇到的數字。
        used = [False] * (len_grid * len_grid + 1)
        
        # 遍歷二維矩陣中的每個元素。
        for row in grid:
            for num in row:
                # 檢查數字是否已經出現過；如果是，將其賦值給 'repeated_num'。
                if used[num]:
                    repeated_num = num
                used[num] = True  # 將數字標記為已遇到。
        
        # 通過檢查 'used' 列表來找到缺失的數字。
        for i in range(1, len_grid * len_grid + 1):
            if not used[i]:
                return [repeated_num, i]
        
        # 如果邏輯失敗，則默認返回，然而根據約束條件不應該發生。
        return [-1, -1]

複雜度分析

• 時間複雜度: $O(n^2)$，其中 $n$ 是網格中一維的大小。這是因為演算法在第一次巢狀迴圈中遍歷 $n \times n$ 網格中的每個元素，以標記已使用的數字。第二個迴圈最多運行 $n^2$ 次以找到缺失的數字，這由相同的因子 $n^2$ 限制。因此，整體時間複雜度為 $O(n^2) + O(n^2) = O(n^2)$。

• 空間複雜度: 空間複雜度是 $O(n^2)$。這源於「used」向量，其大小為 $n^2 + 1$，以容納從 $1$ 到 $n^2$ 的所有數字。其他變數使用固定空間。因此，主要的空間需求來自「used」向量，導致空間複雜度為 $O(n^2)$。