find duplicate

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.

Note

• 正负标记法
• 遍历数组，记index = Math.abs( nums[i] ) - 1（因为nums[index] 在[1, n]，减1则index在[0, n-1]），将index作为数组nums的下标。
• 当 n 首次出现，nums[index] 乘以-1。
• 当 n 再次出现，则 nums[index] < 0，将nums[i]加入res。

Extension

• 数组中查找重复元素，使用正负标记方法，或者其他标记方法。

Solution

public List<Integer> findDuplicate(int[] nums) {
    List<Integer> res = new ArrayList<>();
    if  (nums.length < 1) {
        return res;
    }
    for (int i = 0; i < nums.length; i++) {
        int index = Math.abs(nums[i]) - 1;    // 获取index
        if (nums[index] < 0) {    // 已经被标记过一次
            res.add(index + 1);
        } else {    // 首次遇到，取反，标记一次。
            nums[index] = -nums[index];
        }
    }
}