Find Duplicate 系列

经典题目

1 <= a[i] <= n, a.length == n + 1, find the duplicate one.

找到正确位置法：把所有数都放到正确的位置上，即a[i] = i，那么必然有一个数的位置是错的。

287 Find the Duplicate Number

// T/O(n), S/O(1)

1 <= a[i] <= n, a.length == n, some appear twice and others appear once.

Mark 法：借助原有array的index来标记已经出现过的数。

我们把遇到过的value用相等的index来记录。比如，a[0] = 4，那我们查看a[3]的值（因为1 <= a[i] <= n，所以这里要减一），若a[3] < 0，则 4 即为重复的数。如a[3] > 0，则把a[3]的数置负。

442 Find All Duplicates in an Array

// T/O(n), S/O(1)
public List<Integer> findDuplicates(int[] nums) {
    List<Integer> ans = new ArrayList<>();
    for (int i = 0; i < nums.length; i++) {
        int index = Math.abs(nums[i]) - 1;
        if (nums[index] > 0) {
            nums[index] = -nums[index];
        } else {
            ans.add(index + 1);
        }
    }
    return ans;
}