442. Find All Duplicates in an Array

QUESTION

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]

THOUGHT I

先排个序就好找了，时间复杂度为O(nlogn)，不符合要求

CODE

public class Solution {
    public List<Integer> findDuplicates(int[] nums) {
        List<Integer> res = new ArrayList<>();
        if(nums == null || nums.length == 0 || nums.length == 1)
            return res;
        Arrays.sort(nums);
        for(int i = 0;i < nums.length - 1;i++){
            if(nums[i] == nums[i + 1])
                res.add(nums[i]);
        }
        return res;
    }
}

THOUGHT II

题中给出了一个很好的条件，那就是1 ≤ a[i] ≤ n，也就是说0<= a[i] - 1<=n-1,刚好是数组的下标的范围。我们可以利用这个搞点事情，从头开始遍历数组，把下标nums[i]对应的数组元素变为负数，如果元素重复，则其对应的元素应为负数

CODE

public class Solution {
    public List<Integer> findDuplicates(int[] nums) {
        List<Integer> res = new ArrayList<>();
        if(nums == null || nums.length == 0 || nums.length == 1)
            return res;
        for(int i = 0;i < nums.length;i++){
            int loc = Math.abs(nums[i]) - 1;
            if(nums[loc] < 0)
                res.add(Math.abs(nums[i]));
            else
                nums[loc] = -nums[loc];
        }
        return res;
    }
}