Array
Hash Table
Description
Given an integer array nums
of length n
where all the integers of nums
are in the range [1, n]
and each integer appears at most 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 auxiliary space, excluding the space needed to store the output
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 .
Solutions
Solution 1
Python3 Java C++ Go
class Solution :
def findDuplicates ( self , nums : List [ int ]) -> List [ int ]:
for i in range ( len ( nums )):
while nums [ i ] != nums [ nums [ i ] - 1 ]:
nums [ nums [ i ] - 1 ], nums [ i ] = nums [ i ], nums [ nums [ i ] - 1 ]
return [ v for i , v in enumerate ( nums ) if v != i + 1 ]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23 class Solution {
public List < Integer > findDuplicates ( int [] nums ) {
int n = nums . length ;
for ( int i = 0 ; i < n ; ++ i ) {
while ( nums [ i ] != nums [ nums [ i ] - 1 ] ) {
swap ( nums , i , nums [ i ] - 1 );
}
}
List < Integer > ans = new ArrayList <> ();
for ( int i = 0 ; i < n ; ++ i ) {
if ( nums [ i ] != i + 1 ) {
ans . add ( nums [ i ] );
}
}
return ans ;
}
void swap ( int [] nums , int i , int j ) {
int t = nums [ i ] ;
nums [ i ] = nums [ j ] ;
nums [ j ] = t ;
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18 class Solution {
public :
vector < int > findDuplicates ( vector < int >& nums ) {
int n = nums . size ();
for ( int i = 0 ; i < n ; ++ i ) {
while ( nums [ i ] != nums [ nums [ i ] - 1 ]) {
swap ( nums [ i ], nums [ nums [ i ] - 1 ]);
}
}
vector < int > ans ;
for ( int i = 0 ; i < n ; ++ i ) {
if ( nums [ i ] != i + 1 ) {
ans . push_back ( nums [ i ]);
}
}
return ans ;
}
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14 func findDuplicates ( nums [] int ) [] int {
for i := range nums {
for nums [ i ] != nums [ nums [ i ] - 1 ] {
nums [ i ], nums [ nums [ i ] - 1 ] = nums [ nums [ i ] - 1 ], nums [ i ]
}
}
var ans [] int
for i , v := range nums {
if v != i + 1 {
ans = append ( ans , v )
}
}
return ans
}
GitHub