442. Find All Duplicates in an Array

  • 55.9%

https://leetcode.com/problems/find-all-duplicates-in-an-array/

Given an array of integers, 1 ≤ a[i] ≤ n (n = size of array), some elements appear twice and others appear once.

Find all the elements that appear twice in this array.

Could you do it without extra space and in O(n) runtime?

1
2
3
4
5
6
Example:
Input:
[4,3,2,7,8,2,3,1]

Output:
[2,3]

方法一:

https://discuss.leetcode.com/topic/64759/very-simple-c-solution

Very simple C++ solution

Firstly, we put each element x in nums[x - 1]. Since x ranges from 1 to N, then x - 1 ranges from 0 to N - 1, it won’t exceed the bound of the array.
Secondly, we check through the array. If a number x doesn’t present in nums[x - 1], then x is absent.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
vector<int> findDuplicates(vector<int>& nums) {
vector<int> res;
int i = 0;
while (i < nums.size()) {
if (nums[i] != nums[nums[i]-1]) swap(nums[i], nums[nums[i]-1]);
else i++;
}
for (i = 0; i < nums.size(); i++) {
if (nums[i] != i + 1) res.push_back(nums[i]);
}
return res;
}
};

我的代码实现:

第一遍,先交换,将不对应的全部交还。

第二遍,找出不对应的。

这个分为两步,然后处理。不放在同一个步骤,清晰明了,值得学习。

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) {
vector<int> res;
int n = nums.size();
int i=0;
while(i<n){
if(nums[i]!=nums[nums[i]-1])
swap(nums[i], nums[nums[i]-1]);
else
i++;
}
for(int i=0; i<n; i++)
if(nums[i]!=i+1)
res.push_back(nums[i]);
return res;
}
};

https://discuss.leetcode.com/topic/64835/c-easy-o-n-time-and-o-1-extra-space-solution-through-swapping

C++ Easy O(n) time and O(1) extra space solution through swapping.

Given that each element is between 1 and n. All the elements occur either once or twice.

So, in first pass, we can swap all the elements to their respective positions.

In second pass, all the one-time occuring elements are supposed to be at their positions. The elements that violate this conditions are the elements of our interest (because they are at some other positions, in addition of being at their respective index, where they are not supposed to be).

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:
vector<int> findDuplicates(vector<int>& nums) {
if(nums.empty()) return {};
vector<int> res;
int n = nums.size();
for(int i = 0; i < n; i++)
nums[i]-=1; //for indexing flexibility

int i = 0;
while(i < n) {
if(nums[i] != nums[nums[i]])
swap(nums[i], nums[nums[i]]); //swap elements to their respective indexes.
else
i++;
}
for(int i = 0; i < n; i++) {
if(nums[i] != i)
res.push_back(nums[i]+1); //get the elements which are at some other indexes (as they are occuring twice)
}
return res;
}
};

https://discuss.leetcode.com/topic/64903/c-using-another-idea-instead-of-swapping

C++ using another idea instead of swapping

idea: take advantage of sign bit in integer

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
vector<int> findDuplicates(vector<int>& nums) {
vector<int> ret;
int mark = 0x80000000;
int mask = 0x7fffffff;
for (int i = 0; i < nums.size(); ++i){
int num = nums[i] & mask;
if (nums[num - 1] & mark)
ret.push_back(num);
nums[num - 1] |= mark;
}
return ret;
}
};

python

https://discuss.leetcode.com/topic/64979/python-o-n-time-o-1-space

Python O(n) time O(1) space

O(1) space not including the input and output variables

The idea is we do a linear pass using the input array itself as a hash to store which numbers have been seen before. We do this by making elements at certain indexes negative. See the full explanation here

http://www.geeksforgeeks.org/find-duplicates-in-on-time-and-constant-extra-space/

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution(object):
def findDuplicates(self, nums):
"""
:type nums: List[int]
:rtype: List[int]
"""
res = []
for x in nums:
if nums[abs(x)-1] < 0:
res.append(abs(x))
else:
nums[abs(x)-1] *= -1
return res

java

https://discuss.leetcode.com/topic/64735/java-simple-solution

Java Simple Solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public class Solution {
// when find a number i, flip the number at position i-1 to negative.
// if the number at position i-1 is already negative, i is the number that occurs twice.

public List<Integer> findDuplicates(int[] nums) {
List<Integer> res = new ArrayList<>();
for (int i = 0; i < nums.length; ++i) {
int index = Math.abs(nums[i])-1;
if (nums[index] < 0)
res.add(Math.abs(index+1));
nums[index] = -nums[index];
}
return res;
}
}

https://discuss.leetcode.com/topic/64908/java-solution-without-destroying-the-input-array-o-n-time-o-1-space

Java solution without destroying the input array. O(n) time. O(1) space.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public List<Integer> findDuplicates(int[] nums) {
List<Integer> result = new ArrayList<Integer>();
if(nums == null)
return result;
for(int i=0; i<nums.length; i++){
int location = Math.abs(nums[i])-1;
if(nums[location] < 0){
result.add(Math.abs(nums[i]));
}else{
nums[location] = -nums[location];
}
}
for(int i=0; i<nums.length; i++)
nums[i] = Math.abs(nums[i]);

return result;
}

https://discuss.leetcode.com/topic/64805/java-easy-to-understand-solution-without-extra-space-and-in-o-n-time

Java Easy to understand solution without extra space and in O(n) time

The concept here is to negate each number’s index as the input is 1 <= a[i] <= n (n = size of array). Once a value is negated, if it requires to be negated again then it is a duplicate.

1
2
3
4
5
6
7
8
9
10
11
12
13
public List<Integer> findDuplicates(int[] nums) {
List<Integer> newList = new ArrayList<Integer>(); // creating a new List
for(int i=0;i<nums.length;i++){
int index =Math.abs(nums[i]); // Taking the absolute value to find index
if(nums[index-1] >0){
nums[index-1] = - nums[index-1];
}else{
// If it is not greater than 0 (i.e) negative then the number is a duplicate
newList.add(Math.abs(nums[i]));
}
}
return newList;
}
谢谢你,可爱的朋友。