442. Find All Duplicates in an Array
442. Find All Duplicates in an Array
题目
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
,可以通过修改原数组的方式来标记出现过的元素。
具体的步骤如下:
- 遍历数组,对于每个元素
nums[i]
,将其对应的索引处的元素取反。 - 当访问到某个元素
nums[j]
时,如果nums[j]
已经是负数,说明之前已经访问过,表示j+1
是重复出现的元素。 - 将找到的重复元素添加到结果数组中。
- 时间复杂度:
O(n)
,其中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;
};
相关题目
相关题目
- [448. 找到所有数组中消失的数字](https://leetcode.com/problems/find-all-numbers-disappeared-in-an-array)
- [2615. 等值距离和](https://leetcode.com/problems/sum-of-distances)