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]

https://blog.csdn.net/haolexiao/article/details/53487436
如果采用不断swap的方法，最后缺失的位置上会剩下重复的元素。如果采用轮换替换的方法，则会变得麻烦。

    vector<int> findDuplicates(vector<int>& nums) {
        vector<int> res;
        for(int i=0;i<nums.size();i++){
            while(nums[i] != nums[nums[i]-1])
                swap(nums[i],nums[nums[i]-1]);
        }
        for(int i=0;i<nums.size();i++)
            if(nums[i]!=i+1)
                res.push_back(nums[i]);
        return res;
    }

http://bookshadow.com/weblog/2016/10/25/leetcode-find-all-duplicates-in-an-array/
解法II 位置交换法

遍历nums，记当前下标为i

当nums[i] > 0 并且 nums[i] != i + 1时，执行循环：

令n = nums[i]

如果n == nums[n - 1]，则将n加入答案，并将nums[i]置为0

否则，交换nums[i], nums[n - 1]

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

解法I 正负号标记法（一趟遍历）

https://leetcode.com/problems/find-all-duplicates-in-an-array/discuss/92448/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){
            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://leetcode.com/problems/find-all-duplicates-in-an-array/discuss/92387/Java-Simple-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/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)
                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/

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;
}