# 0442. Find All Duplicates in an Array
###### tags: `Leetcode` `Medium` `Indexing Sort`
Link: https://leetcode.com/problems/find-all-duplicates-in-an-array/
## 思路 $O(N)$ $O(1)$
和[0287. Find the Duplicate Number](https://hackmd.io/hxOTm-zKQUKWmdoBsWVXYg)类似
### Negative Marking
由于数字的范围是[1,n]，所以可以直接在原本的array上面标记，把找出现过的数字对应的值，把它变成负的，那么出现两次的就会是正值
### Swap
我们希望```nums```array里面所有```idx```都满足```nums[i]=i+1```
所以我们需要一直循环交换```nums[i]```和```nums[nums[i]-1]```
直到我们发现```nums[nums[i]-1]==nums[i]```也就是当前数字```nums[i]```已经在正确的位置了 也就表明找到了一个重复数字
如果while回圈里面用```i==nums[i]-1```做条件就会无穷回圈 因为可能永远满足不了
所以我们实际上是需要满足让```nums[i]```现在存的数字是在对的位置上
例如```[1,1,2]```, 当```i=1```时会进入回圈 因为已经有一个1在对的位置上了 所以我们不管这个1
当```i=2```时才会把后面的1和2交换
## Code
### Negative Marking

class Solution {
    public List<Integer> findDuplicates(int[] nums) {
        List<Integer> ans = new ArrayList<>();
        for(int num:nums){
            nums[Math.abs(num)-1] *= -1;
        }
        for(int num:nums){
            if(nums[Math.abs(num)-1] > 0){
                ans.add(Math.abs(num));
                nums[Math.abs(num)-1] *= -1;
            }
        }
        return ans;
    }
}

### Swap

class Solution {
    public List<Integer> findDuplicates(int[] nums) {
        int n = nums.length;
        List<Integer> ans = new ArrayList<>();
        for(int i=0; i<n; i++){
            if(nums[i]!=i+1){
                while(nums[i] != nums[nums[i]-1]){
                    swap(nums, i, nums[i]-1);
                }
            }
        }
        for(int i=0; i<n; i++){
            if(nums[i]!=i+1) ans.add(nums[i]);
        }
        return ans;
    }
    private void swap(int[] nums, int idx1, int idx2){
        int temp = nums[idx1];
        nums[idx1] = nums[idx2];
        nums[idx2] = temp;
    }
}