- 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 | Example: |

方法一：

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 | class Solution { |

我的代码实现：

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

第二遍，找出不对应的。

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

1 | class Solution { |

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 | class Solution { |

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 | class Solution { |

#### 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 | class Solution(object): |

#### java

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

Java Simple Solution

1 | public class Solution { |

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

1 | public List<Integer> findDuplicates(int[] nums) { |

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 | public List<Integer> findDuplicates(int[] nums) { |