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

🟢   🔖  数组 哈希表 数学 矩阵  🔗 力扣 LeetCode

题目

You are given a 0-indexed 2D integer matrix grid of size n * n with values in the range [1, n2]. Each integer appears exactly once except a which appears twice and b which is missing. The task is to find the repeating and missing numbers a and b.

Return _a 0-indexed integer array _ans of size2whereans[0]equals toa andans[1]equals tob .

Example 1:

Input: grid = [[1,3],[2,2]]

Output: [2,4]

Explanation: Number 2 is repeated and number 4 is missing so the answer is [2,4].

Example 2:

Input: grid = [[9,1,7],[8,9,2],[3,4,6]]

Output: [9,5]

Explanation: Number 9 is repeated and number 5 is missing so the answer is [9,5].

Constraints:

• 2 <= n == grid.length == grid[i].length <= 50
• 1 <= grid[i][j] <= n * n
• For all x that 1 <= x <= n * n there is exactly one x that is not equal to any of the grid members.
• For all x that 1 <= x <= n * n there is exactly one x that is equal to exactly two of the grid members.
• For all x that 1 <= x <= n * n except two of them there is exatly one pair of i, j that 0 <= i, j <= n - 1 and grid[i][j] == x.

题目大意

给你一个下标从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 。

解题思路

思路一：数学法

设：缺失的数 y，重复的数 x，可以列出 两条数学公式：

1. 和的公式：

   • 记 expectSum 为 [1, 2, ..., n^2] 的总和，actualSum 为 grid 中所有数的和：
   • y - x = expectSum - actualSum
   • 记为：diffSum。

2. 平方和的公式：

   • 记 expectSquareSum 为 [1, 2, ..., n^2] 的平方和，actualSquareSum 为 grid 中所有数的平方和：
   • y^2 - x^2 = expectSquareSum - actualSquareSum
   • 记为：diffSquareSum。

3. 解出 y 和 x

   • y^2 - x^2 可转换为：(y-x)(y+x)
   • 代入 y - x，可得：y + x = diffSquareSum / diffSum
   • 联立两个等式：
     • y = (diffSquareSum / diffSum + diffSum) / 2
     • x = (diffSquareSum / diffSum - diffSum) / 2

复杂度分析

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

  • 计算 expectSquareSum 需要 O(n^2)
  • 遍历 grid 计算 actualSum 和 actualSquareSum 需要 O(n^2)
  • 计算 x 和 y 仅需 O(1)

• 空间复杂度：O(1)，仅使用常数级变量存储 expectSum, actualSum，所以是 O(1)

---

思路二：数组标记法

1. 使用数组 exists 标记出现的数字

• 创建一个长度为 n^2 的布尔数组 exists，用于标记每个数是否出现过。
• 遍历 grid：
  • 如果当前数 num 已经在 exists 数组中被标记，则说明 它是重复的数 x。
  • 否则，标记 exists[num - 1] = true。

2. 找到 exists 中 false 的索引

• 再次遍历 exists，找到 第一个 false 的位置 i，说明 i+1 是缺失的数 y。

复杂度分析

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

  • 遍历 grid 需要 O(n^2)
  • 遍历 exists 数组需要 O(n^2)
  • 总体 O(n^2)

• 空间复杂度：O(n^2)，额外使用了 exists 数组，大小 O(n^2)

代码

数学法

/**
 * @param {number[][]} grid
 * @return {number[]}
 */
var findMissingAndRepeatedValues = function (grid) {
	const n = grid.length;
	const expectSum = ((1 + n * n) * n * n) / 2; // 期望的总和
	let expectSquareSum = 0; // 期望的平方和

	for (let i = 1; i <= n * n; i++) {
		expectSquareSum += i * i;
	}

	let actualSum = 0,
		actualSquareSum = 0;

	for (let row of grid) {
		for (let num of row) {
			actualSum += num;
			actualSquareSum += num * num;
		}
	}

	const diffSum = expectSum - actualSum; // y - x
	const diffSquareSum = expectSquareSum - actualSquareSum; // y^2 - x^2

	const missing = (diffSquareSum / diffSum + diffSum) / 2;
	const repeated = (diffSquareSum / diffSum - diffSum) / 2;

	return [repeated, missing];
};

数组标记法

/**
 * @param {number[][]} grid
 * @return {number[]}
 */
var findMissingAndRepeatedValues = function (grid) {
	const n = grid.length;
	let repeated, missing;
	let exists = new Array(n * n).fill(false);

	// 1. 找到重复的数字，并标记出现的数字
	for (let row of grid) {
		for (let num of row) {
			if (exists[num - 1] == true) {
				repeated = num;
			}
			exists[num - 1] = true;
		}
	}

	// 2. 找到缺失的数字
	for (let i = 0; i < n * n; i++) {
		if (exists[i] == false) {
			missing = i + 1;
			break;
		}
	}

	return [repeated, missing];
};