## Wednesday, October 26, 2016

### LeetCode 442 - Find All Duplicates in an Array

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?
Example:
```Input:
[4,3,2,7,8,2,3,1]

Output:
[2,3]
```

```遍历nums，记当前数字为n（取绝对值），将数字n视为下标（因为a[i]∈[1, n]）

def findDuplicates(self, nums): """ :type nums: List[int] :rtype: List[int] """ ans = [] for n in nums: if nums[abs(n) - 1] < 0: ans.append(abs(n)) else: nums[abs(n) - 1] *= -1 return ans

https://discuss.leetcode.com/topic/64735/java-simple-solution
https://discuss.leetcode.com/topic/64805/java-easy-to-understand-solution-without-extra-space-and-in-o-n-time
``````    // 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)
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/
``````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){
}else{
nums[location] = -nums[location];
}
}
for(int i=0; i<nums.length; i++)
nums[i] = Math.abs(nums[i]);

return result;
}``````
```遍历nums，记当前下标为i

def findDuplicates(self, nums): """ :type nums: List[int] :rtype: List[int] """ ans = [] for i in range(len(nums)): while nums[i] and nums[i] != i + 1: n = nums[i] if nums[i] == nums[n - 1]: ans.append(n) nums[i] = 0 else: nums[i], nums[n - 1] = nums[n - 1], nums[i] return ans