LeetCode Notes: Find All Duplicates in an Array
Question
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 <= 105
1 <= nums[i] <= n
- Each element in
nums
appears once or twice.
Solution One
Analysis:
Use the unique feature of Set
to continuously add the numbers in nums
to an empty Set
, and then use the set.add
method to determine whether there are repeated numbers by getting the length of set
to increase.
Code:
/**
* @param {number[]} nums
* @return {number[]}
*/
var findDuplicates = function (nums) {
const set = new Set(); // unique value test
const result = []; // result array
nums.forEach((n) => {
const preSize = set.size;
// Use the set.add method to determine whether there are duplicate numbers by getting the length of the set to increase
set.add(n);
// find duplicate numbers
if (preSize === set.size) {
result.push(n);
}
});
return result;
};
Solution Two
Analysis:
Traverse the entire array, treat each number as the array position information, and then reverse the number corresponding to each position to a negative number, which is equivalent to making a mark, indicating that the position corresponding to this number is already occupied by a number, and we will meet again next time If this number is found to be negative, it means that it has already appeared.
For example [4,3,2,7,8,2,3,1]
, when reaching the first 2
, the number 3
whose position is 1
is flipped to -3
, go By the next 2
, the number -3
in position 1
can be found, which has been flipped, indicating that the number 2
occurs twice.
Code:
/**
* @param {number[]} nums
* @return {number[]}
*/
var findDuplicates = function(nums) {
let result = [];
for (let i = 0; i < nums.length; i++) {
let num = Math.abs(nums[i]);
if (nums[num - 1] > 0) {
/**
The purpose of flipping the number to a negative number is to make a mark to indicate that the position corresponding to the number is already occupied by a number. If the number is found to be a negative number next time, it means that it has already appeared.
For example [4,3,2,7,8,2,3,1]
When you go to the first 2, the number in position 1 is 3, flip the 3 to -3, and when you go to the next 2, when you flip 3, you find that it has been flipped.
*/
nums[num - 1] *= -1;
} else {
result.push(num);
}
}
return result;
};
Comments