🔗 🟢 2965. Find Missing and Repeated Values 1245

tags: `Weekly Contest 376` `計數(Counter)` `雜湊表(Hash Table)` `位運算(Bit Manipulation)` `數學(Math)`

題意

給定一個下標從 $0$ 開始的二維整數矩陣 $grid$ ，大小為 $n \times n$ ，其中的值皆在 $[1, n^2]$ 範圍內。

$grid$ 中除了 $a$ 出現兩次， $b$ 缺失之外，每個整數都 恰好出現一次。以長度為 $2$ 的列表形式返回重複的數字 $a$ 和缺失的數字 $b$ ，需按照 $[a, b]$ 的順序返回。

思路

方法一：計數(Counter) / 雜湊表(Hash Table)

根據題意 $grid[i][j]$ 的值域為 $[1, n^2]$ ，因此可以使用一個長度為 $n^2+1$ 的陣列或雜湊表 $cnt$ 來計算每個數字出現的次數，最後找出出現兩次的數字和沒有出現的數字即可。

複雜度分析

時間複雜度 $\mathcal{O}(n^2)$
空間複雜度 $\mathcal{O}(n^2)$

class Solution:
    def findMissingAndRepeatedValues(self, grid: List[List[int]]) -> List[int]:
        n = len(grid)
        cnt = [0] * (n * n + 1)
        for row in grid:
            for x in row:
                cnt[x] += 1
        ans = [-1, -1]
        for i in range(1, n * n + 1):
            if cnt[i] == 2: # repeated, a
                ans[0] = i
            elif cnt[i] == 0: # missing, b
                ans[1] = i
        return ans

class Solution {
public:
    vector<int> findMissingAndRepeatedValues(vector<vector<int>>& grid) {
        int n = grid.size();
        unordered_map<int, int> cnt;
        for (int i=0; i<n; i++)
            for (int j=0; j<n; j++)
                cnt[grid[i][j]]++;
        vector<int> ans(2);
        for (int i=1; i<=n*n; i++){
            if (cnt[i] == 2) ans[0] = i; // repeated, a
            else if (cnt[i] == 0) ans[1] = i; // missing, b
        }
        return ans;
    }
};

方法二：位運算(Bit Manipulation)

將 $grid$ 視為長度為 $n^2$ 的一維陣列，若在 $grid$ 中額外添加 $[1, n^2]$ 的所有數字，則在 $[1, n^2]$ 中重複的數字 $a$ 會出現三次、缺失的數字 $b$ 會出現一次，其餘數字皆會出現兩次。

如此便可以將此問題轉換為 260. Single Number III 的問題，使用位運算來找出 $a$ 和 $b$ 。過程可以參考該題的解題紀錄，這裡不再贅述。

但需注意，在該題中返回的順序是任意的，而這題要求返回的順序是 $[a, b]$ ，因此在最後需要檢查 $a$ 是否在 $grid$ 中，若不在則將 $a$ 和 $b$ 交換。

複雜度分析

時間複雜度 $\mathcal{O}(n^2)$
空間複雜度 $\mathcal{O}(1)$

class Solution:
    def findMissingAndRepeatedValues(self, grid: List[List[int]]) -> List[int]:
        n = len(grid)
        # 異或所有數字
        xor = 0 # xor of all numbers
        for row in grid:
            for x in row:
                xor ^= x
        for x in range(1, n * n + 1):
            xor ^= x
        # 分組異或
        lb = xor & -xor # 最低位的 1
        ans = [0, 0]
        for row in grid:
            for x in row:
                ans[x & lb == 0] ^= x # 分組異或
        for x in range(1, n * n + 1):
            ans[x & lb == 0] ^= x # 分組異或
        return ans if ans[0] in [x for row in grid for x in row] else ans[::-1]

class Solution {
public:
    vector<int> findMissingAndRepeatedValues(vector<vector<int>>& grid) {
        int n = grid.size();
        // xor all numbers
        int s = 0; // xor of all numbers
        for (int i=0; i<n; i++)
            for (int j=0; j<n; j++)
                s ^= grid[i][j];
        for (int i=1; i<=n*n; i++)
            s ^= i;
        // group xor
        int lb = s & -s; // lowest bit of 1
        vector<int> ans(2);
        for (int i=0; i<n; i++)
            for (int j=0; j<n; j++)
                ans[(grid[i][j] & lb) == 0] ^= grid[i][j];
        for (int i=1; i<=n*n; i++)
            ans[(i & lb) == 0] ^= i;
        // check if ans[0] is in grid
        for (auto& row : grid)
            if (find(row.begin(), row.end(), ans[0]) != row.end())
                return ans;
        return {ans[1], ans[0]};
    }
};

方法三：數學(Math)

令 $m = n^2$ ， $grid$ 中的所有元素和為 $s_1$ ，所有元素的平方和為 $s_2$ 。若將 $[1, m]$ 的所有數字相加，則總和為 $\sum_{i=1}^{n^2} i = \frac{m(m+1)}{2}$ ；將 $[1, m]$ 的所有數字的平方相加，則總和為 $\sum_{i=1}^{n^2} i^2 = \frac{m(m+1)(2m+1)}{6}$ 。

由於在 $grid$ 中 $a$ 出現兩次， $b$ 缺失，因此 $s1$ 和 $s2$ 會比 $\frac{m(m+1)}{2}$ 和 $\frac{m(m+1)(2m+1)}{6}$ 多 $a - b$ 和 $a^2 - b^2$ ，即 $a - b = s_1 - \frac{m(m+1)}{2}$ 和 $a^2 - b^2 = s_2 - \frac{m(m+1)(2m+1)}{6}$ ，分別令為 $d1$ 和 $d2$ 。

聯立 $d1 = a - b$ 和 $d2 = a^2 - b^2 = (a + b)(a - b)$ ，即可解出 $a$ 和 $b$ 。

兩式相除得到 $a + b = \frac{d2}{d1}$
$\frac{d2}{d1} + d1 = 2a \Rightarrow a = \frac{\frac{d2}{d1} + d1}{2}$
$\frac{d2}{d1} - d1 = 2b \Rightarrow b = \frac{\frac{d2}{d1} - d1}{2}$

複雜度分析

時間複雜度 $\mathcal{O}(n^2)$ ，計算 $s1$ 和 $s2$ 需要遍歷整個 $grid$
空間複雜度 $\mathcal{O}(1)$

class Solution:
    def findMissingAndRepeatedValues(self, grid: List[List[int]]) -> List[int]:
        n, m = len(grid), len(grid) ** 2
        s1 = sum(x for row in grid for x in row) # sum of all numbers
        s2 = sum(x * x for row in grid for x in row) # sum of all squares
        d1 = s1 - m * (m + 1) // 2 # a - b
        d2 = s2 - m * (m + 1) * (m * 2 + 1) // 6 # a^2 - b^2 = (a + b)(a - b)
        return [(d2 // d1 + d1) // 2, (d2 // d1 - d1) // 2] # (a, b)

using LL = long long;
class Solution {
public:
    vector<int> findMissingAndRepeatedValues(vector<vector<int>>& grid) {
        int n = grid.size();
        LL m = n * n, d1 = 0, d2 = 0;
        for (int i=0; i<n; i++)
            for (int j=0; j<n; j++){
                d1 += grid[i][j]; // sum of all numbers
                d2 += grid[i][j] * grid[i][j]; // sum of all squares
            }
        d1 -= m * (m + 1) / 2; // a - b
        d2 -= m * (m + 1) * (m * 2 + 1) / 6; // a^2 - b^2 = (a + b)(a - b)
        return {(int) (d2 / d1 + d1) / 2, (int) (d2 / d1 - d1) / 2}; // (a, b)
    }
};