石家庄建站模板,专门做男装的网站,外贸网站wordpress加ssl,网站开发前端课程【LetMeFly】2965.找出缺失和重复的数字#xff1a;小数据#xff1f;我选择暴力#xff08;附优化方法清单#xff1a;O(1)空间方法3#xff09;
力扣题目链接#xff1a;https://leetcode.cn/problems/find-missing-and-repeated-values/
给你一个下标从 0 开始的二维…【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 501 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 n^21 n21的数组用来记录每个数分别出现了多少次。
遍历原始数组即可完成计数数组遍历计数数组即可得到答案。
时间复杂度 O ( n 2 ) O(n^2) O(n2)空间复杂度 O ( n 2 ) O(n^2) O(n2)
AC代码
C
class Solution {
public:vectorint findMissingAndRepeatedValues(vectorvectorint grid) {vectorint times(grid.size() * grid.size() 1);for (vectorint line : grid) {for (int t : line) {times[t];}}vectorint 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 t出现过就将数组中第 t t t个元素置为负数若某次将某元素置为负数时发现已经是负数了则说明这个数出现了两次。到最后也没被置为负数的位置说明对应的数没有出现。 优化方法二数学方法 ∑ i 1 n 2 i − ∑ g r i d b − a \sum_{i1}^{n^2}i-\sum gridb-a ∑i1n2i−∑gridb−a一个方程不足以解出两个变量因此可以再加一个方程。 例如 ∑ i 1 n 2 i 2 − ∑ i ∈ g r i d i 2 b 2 − a 2 \sum_{i1}^{n^2}i^2-\sum_{i\in grid} i^2b^2-a^2 ∑i1n2i2−∑i∈gridi2b2−a2联立两方程即可得到 a a a和 b b b的值。 优化方法三位运算 根据异或的性质异或一个数偶数次相当于没有异或。因此假设异或grid中的每个元素再异或从1到 n 2 n^2 n2得到结果 t t t则 t a ⊕ b ta\oplus b ta⊕b相当于 a a a一共异或了3次而 b b b一共异或了1次。 到这里很多同学都看出了这题本质和260. 只出现一次的数字 III相同。 如何拆分 a a a和 b b b依据两个原则分别异或即可。假设 t t t二进制下第一个 1 1 1是第 2 2 2位则所有数依据第 2 2 2位是否为 1 1 1分为两种。每组中所有元素相互异或最终的两个结果就是 a a a和 b b b。 这里“所有数”是指 1 1 1到 n 2 n^2 n2的所有数以及原始数组中的所有数。 为什么这样能将 a a a和 b b b分开因为根据异或结果 t t t可得 a a a和 b b b二进制下第 2 2 2位绝对不同因此 a a a和 b b b会被分到两个不同的组中。每个组中除了 a a a或 b b b都出现偶数次因此两组的异或结果就是 a a a和 b b b。 End 同步发文于CSDN和我的个人博客原创不易转载经作者同意后请附上原文链接哦~ Tisfyhttps://letmefly.blog.csdn.net/article/details/139357662
