2965.找出缺失和重复的数字

【LetMeFly】2965.找出缺失和重复的数字：小数据？我选择暴力（附优化方法清单：O(1)空间方法×3）

力扣题目链接：https://leetcode.cn/problems/find-missing-and-repeated-values/

给你一个下标从 0 开始的二维整数矩阵 grid，大小为 n * n ，其中的值在 [1, n2] 范围内。除了 a 出现 两次，b 缺失 之外，每个整数都 恰好出现一次 。

任务是找出重复的数字a 和缺失的数字 b 。

返回一个下标从 0 开始、长度为 2 的整数数组 ans ，其中 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 <= n == grid.length == grid[i].length <= 50
• 1 <= grid[i][j] <= n * n
• 对于所有满足1 <= x <= n * n 的 x ，恰好存在一个 x 与矩阵中的任何成员都不相等。
• 对于所有满足1 <= x <= n * n 的 x ，恰好存在一个 x 与矩阵中的两个成员相等。
• 除上述的两个之外，对于所有满足1 <= x <= n * n 的 x ，都恰好存在一对 i, j 满足 0 <= i, j <= n - 1 且 grid[i][j] == x 。

解题方法：计数（模拟）

开辟一个$n^2+1$的数组，用来记录每个数分别出现了多少次。

遍历原始数组即可完成计数数组，遍历计数数组即可得到答案。

• 时间复杂度$O(n^2)$
• 空间复杂度$O(n^2)$

AC代码

C++

class Solution {
public:
    vector<int> findMissingAndRepeatedValues(vector<vector<int>>& grid) {
        vector<int> times(grid.size() * grid.size() + 1);
        for (vector<int>& line : grid) {
            for (int t : line) {
                times[t]++;
            }
        }
        vector<int> ans(2);
        for (int i = 1; i < times.size(); i++) {
            if (times[i] == 2) {
                ans[0] = i;
            }
            else if (times[i] == 0) {
                ans[1] = i;
            }
        }
        return ans;
    }
};

时间击败92.71%的提交，空间击败90.28%的提交。

其他方法

本题时间复杂度不可优化，说啥也得至少遍历一遍原始数组。如何优化空间复杂度呢？大致分为三种：

优化方法一：空间的原地使用：

例如$t$出现过就将数组中第$t$个元素置为负数，若某次将某元素置为负数时发现已经是负数了，则说明这个数出现了两次。到最后也没被置为负数的位置说明对应的数没有出现。

优化方法二：数学方法：

$\sum_{i=1}^{n^2}i-\sum grid=b-a$，一个方程不足以解出两个变量，因此可以再加一个方程。

例如$\sum_{i=1}^{n^2}i^2-\sum_{i\in grid} i^2=b^2-a^2$，联立两方程即可得到$a$和$b$的值。

优化方法三：位运算：

根据异或的性质，异或一个数偶数次相当于没有异或。因此假设异或grid中的每个元素再异或从1到$n^2$得到结果$t$，则$t=a\oplus b$（相当于$a$一共异或了3次而$b$一共异或了1次）。

到这里很多同学都看出了这题本质和260. 只出现一次的数字 III相同。

如何拆分$a$和$b$？依据两个原则分别异或即可。假设$t$二进制下第一个$1$是第$2$位，则所有数依据第$2$位是否为$1$分为两种。每组中所有元素相互异或，最终的两个结果就是$a$和$b$。

这里“所有数”是指$1$到$n^2$的所有数以及原始数组中的所有数。

为什么这样能将$a$和$b$分开？因为根据异或结果$t$可得，$a$和$b$二进制下第$2$位绝对不同，因此$a$和$b$会被分到两个不同的组中。每个组中除了$a$或$b$都出现偶数次，因此两组的异或结果就是$a$和$b$。

End

同步发文于CSDN和我的个人博客，原创不易，转载经作者同意后请附上原文链接哦~

Tisfy：https://letmefly.blog.csdn.net/article/details/139357662