645. 错误的集合

🟢   🔖  位运算 数组 哈希表 排序  🔗 力扣 LeetCode

题目

You have a set of integers s, which originally contains all the numbers from 1 to n. Unfortunately, due to some error, one of the numbers in s got duplicated to another number in the set, which results in repetition of one number and loss of another number.

You are given an integer array nums representing the data status of this set after the error.

Find the number that occurs twice and the number that is missing and return them in the form of an array.

Example 1:

Input: nums = [1,2,2,4]

Output: [2,3]

Example 2:

Input: nums = [1,1]

Output: [1,2]

Constraints:

• 2 <= nums.length <= 10^4
• 1 <= nums[i] <= 10^4

题目大意

集合 s 包含从 1 到 n 的整数。不幸的是，因为数据错误，导致集合里面某一个数字复制了成了集合里面的另外一个数字的值，导致集合 丢失了一个数字 并且 有一个数字重复 。

给定一个数组 nums 代表了集合 S 发生错误后的结果。

请你找出重复出现的整数，再找到丢失的整数，将它们以数组的形式返回。

示例 1：

输入： nums = [1,2,2,4]

输出：[2,3]

示例 2：

输入： nums = [1,1]

输出：[1,2]

提示：

• 2 <= nums.length <= 10^4
• 1 <= nums[i] <= 10^4

解题思路

1. 查找重复数字：

   • 通过修改原数组的值来记录数字是否已经出现过。
   • 对于每个数字 num，将 nums[num - 1] 的值取负。
   • 如果 nums[num - 1] 已经是负数，说明 num 已经出现过，则说明这个数字是重复的。

2. 找丢失的数字：遍历数组，找到任何一个仍然是正数的索引，返回该索引加 1 即为丢失的数字。

复杂度分析

• 时间复杂度：O(n)，只遍历了数组两次，时间复杂度是线性的。
• 空间复杂度：O(1)，只使用了常数空间（除了输入和输出数组）。

代码

/**
 * @param {number[]} nums
 * @return {number[]}
 */
var findErrorNums = function (nums) {
	let repeatNum;
	// 第一步：查找重复数字
	for (let num of nums) {
		const idx = Math.abs(num) - 1;
		// 如果该位置是正数，表示没有出现过该数字，改成负数
		if (nums[idx] > 0) {
			nums[idx] *= -1;
		} else {
			// 如果该位置是负数，说明该数字重复
			repeatNum = Math.abs(num);
		}
	}

	// 第二步：查找丢失数字
	for (let i = 0; i < nums.length; i++) {
		if (nums[i] > 0) return [repeatNum, i + 1];
	}
};

相关题目

题号	标题	题解	标签	难度	力扣
287	寻找重复数	[✓]	位运算 数组 双指针 1+	🟠	🀄️ 🔗