leetcode442. 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]

存在一个整数数组，其中的所有元素都位于1~n之间，其中n是数组的长度。有的元素出现了一次，而有的元素出现了两次。找到数组中所有出现两次的数字。

思路一：交换

为了在O(N)的时间内找到所有的出现两次的数字，其核心要求在于用现有的数组记录已经访问过的元素，同时不会丢失尚未访问过的元素。思路一采用交换的核心思想，即每次都将当前下标上的值和以该值为下标的位置上的值进行交换，如果该值下标位置上的值和其相等，则说明该数字已经被遍历过一遍了。

代码如下：

public List<Integer> findDuplicates(int[] nums) {
        int index = 0;
        List<Integer> result = new ArrayList<Integer>();
        while(index < nums.length) {
            int num = nums[index];
            if(num == 0){
                index++;
            }else if (nums[num-1] == num) {
                if(index != num-1){
                    result.add(num);
                    nums[index] = 0;
                }
                index++;
            }else{
                swap(index, num-1, nums);
            }
        }
        return result;
    }
    
    public void swap(int i, int j, int[] nums) {
        int tmp = nums[i];
        nums[i] = nums[j];
        nums[j] = tmp;
    }

思路二：取反

有没有一种办法在既保留当前位置上的值nums[i]的同时，又能够用某种方式记录i+1是否已经被访问过了？可以通过取反的方法来记录是否被访问过这个情况。如果访问到下标为i的位置上的值，则去判断nums[nums[i]-1]位置上的值是否为负数，如果是，则说明num[i]出现了两次，否则将nums[nums[i]-1]位置上的值取反保留。

代码如下：

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