442. 数组中重复的数据

🟠   🔖  数组 哈希表  🔗 力扣 LeetCode

题目

Given an integer array nums of length n where all the integers of nums are in the range [1, n] and each integer appears once or twice , return an array of all the integers that appears twice.

You must write an algorithm that runs in O(n) time and uses only constant extra space.

Example 1:

Input: nums = [4,3,2,7,8,2,3,1]

Output: [2,3]

Example 2:

Input: nums = [1,1,2]

Output: [1]

Example 3:

Input: nums = [1]

Output: []

Constraints:

• n == nums.length
• 1 <= n <= 10^5
• 1 <= nums[i] <= n
• Each element in nums appears once or twice.

题目大意

给你一个长度为 n 的整数数组 nums ，其中 nums 的所有整数都在范围 [1, n] 内，且每个整数出现 一次 或 两次 。请你找出所有出现 两次 的整数，并以数组形式返回。

你必须设计并实现一个时间复杂度为 O(n) 且仅使用常量额外空间的算法解决此问题。

解题思路

题目要求在不使用额外空间和时间复杂度 O(n) 的情况下解决问题。由于 1 <= nums[i] <= n，可以通过修改原数组的方式来标记出现过的元素。

思路一：索引取反

具体的步骤如下：

1. 遍历数组，对于每个元素 nums[i]，将其对应的索引处的元素取反。
2. 当访问到某个元素 nums[j] 时，如果 nums[j] 已经是负数，说明之前已经访问过，表示 j+1 是重复出现的元素。
3. 将找到的重复元素添加到结果数组中。

复杂度分析

• 时间复杂度：O(n)，其中 n 是数组的长度。遍历数组一次。
• 空间复杂度：O(1)，不使用额外的空间。

---

思路二：原地哈希

原地哈希的意思是利用数组的索引来存储元素的存在性。具体来说，将每个值 x 放到数组的索引 x-1 处（即 nums[x-1]），如果 x 的值在 [1, n] 范围内。这样做的前提是，数组中只有正整数。

• 遍历数组：

  • 首先遍历数组，将每个有效的正整数放到正确的位置（即将 x 放到 nums[x-1]）。
  • 对于每个值 x，如果 1 ≤ x ≤ n，并且 nums[x-1] 不是 x，则交换 nums[i] 和 nums[x-1]，直到 nums[i] 在正确的位置。

• 第二次遍历：

  • 再次遍历数组，找到所有 nums[i] 不等于 i + 1 的位置，那么 nums[i] 就是重复的数。

复杂度分析

• 时间复杂度：O(n)，数组只遍历了两次。
• 空间复杂度：O(1)，只使用了常量级别的额外空间。

代码

索引取反

/**
 * @param {number[]} nums
 * @return {number[]}
 */
var findDuplicates = function (nums) {
	let res = [];
	for (let i in nums) {
		const index = Math.abs(nums[i]) - 1;
		if (nums[index] < 0) {
			res.push(index + 1);
		} else {
			nums[index] = -nums[index];
		}
	}
	return res;
};

原地哈希

/**
 * @param {number[]} nums
 * @return {number[]}
 */
var findDuplicates = function (nums) {
	const n = nums.length;
	// 将每个数放到对应的位置
	for (let i = 0; i < n; i++) {
		while (nums[i] !== nums[nums[i] - 1]) {
			// 交换 nums[i] 和 nums[nums[i] - 1]
			let temp = nums[i];
			nums[i] = nums[temp - 1];
			nums[temp - 1] = temp;
		}
	}
	let res = [];
	// 查找没有放在对应位置的正整数，即为重复的数
	for (let i = 0; i < n; i++) {
		if (nums[i] !== i + 1) {
			res.push(nums[i]);
		}
	}
	return res;
};

相关题目

题号	标题	题解	标签	难度
448	找到所有数组中消失的数字		数组 哈希表
2615	等值距离和		数组 哈希表 前缀和
3289	数字小镇中的捣蛋鬼		数组 哈希表 数学