442. 数组中重复的数据

给你一个长度为 n 的整数数组 nums ，其中 nums 的所有整数都在范围 [1, n] 内， 且每个整数出现 一次 或 两次 。请你找出所有出现 两次 的整数，并以数组形式返回。

你必须设计并实现一个时间复杂度为 O(n) 且仅使用常量额外空间的算法解决此问题。

示例 1：

输入：nums = [4,3,2,7,8,2,3,1]
输出：[2,3]

示例 2：

输入：nums = [1,1,2]
输出：[1]

示例 3：

输入：nums = [1]
输出：[]

提示：

• n == nums.length
• 1 <= n <= 105
• 1 <= nums[i] <= n
• nums 中的每个元素出现 一次 或 两次

这道题和448的区别是：这道题规定元素最多出现两次，而不是更多次，因此我们第二次遇到该元素时就可以添加到结果中了。 448的本质在于把问题分成了零次和至少1次，对至少一次的情况，我们可以只在第一次的时候变号，后面就不用操作直接跳过就好了， 因此不管出现多少次，都是第一次的操作结果，即负数，而零次对应的结果就是正数。

用数组模拟哈希集合

如果哈希值是0，则把它变为1，否则找到重复元素。

class Solution {
    public List<Integer> findDuplicates(int[] nums) {
        int n = nums.length;
        // 用数组模拟哈希集合。题目说每个元素都属于[1,n]。seen[i]=1表示值为i的元素出现过，seen[i]=0表示值为i的元素没有出现过。
        int[] seen = new int[n + 1];
        List<Integer> res = new LinkedList<>();
        
        for (int num : nums) {
            if (seen[num] == 0) {
                // 添加到哈希集合
                seen[num] = 1;
            } else {
                // 找到重复元素
                res.add(num);
            }
        }
        return res;
    }
}

• 时间复杂度O(n)
• 空间复杂度O(n)

原地修改

利用元素的取值范围构造映射

假设当前元素值是x，映射关系：x->num[|x| - 1]，因为num中可能有重复的x，所以会访问两次num[|x| - 1]，第一次访问它的时候会把它变为负数，第二次一看是负数，就知道重复了。之所以取绝对值是因为当前值可能被其它值修改了，需要取绝对值获取原值。

1. 遇到一个新元素x，我们根据映射关系x -> num[|x| - 1]把索引num[|x|-1]处的元素变为负数。注意x是元素，num[|x|-1]是索引。
2. 因为num中可能有重复的x，所以会访问两次索引num[|x| - 1]，第一次访问的时候会把该位置的元素变为负数，第二次一看是负数，就知道重复了。
3. 之所以取绝对值是因为当前值可能在操作其它值时被顺便修改了，需要取绝对值获取原值。

class Solution {
    public List<Integer> findDuplicates(int[] nums) {
        List<Integer> res = new LinkedList<>();
        for (int num : nums) {
            // 注意索引，nums 中元素大小从 1 开始，
            // 而索引是从 0 开始的，所以有一位索引偏移
            if (nums[Math.abs(num) - 1] < 0) {
                // 之前已经把对应索引的元素变成负数了，
                // 这说明 num 重复出现了两次
                res.add(Math.abs(num));
            } else {
                // 把索引 num - 1 置为负数
                nums[Math.abs(num) - 1] *= -1;
            }
        }

        return res;
    }
}

• 时间复杂度：O(n)。
• 空间复杂度：O(1)。返回值不计入空间复杂度。

原地交换

利用元素的取值范围构造映射。将元素交换到对应的位置。

元素x应被放在x-1位置处。交换后再遍历一次，对不上的元素就是重复元素。

把每个数都放到正确的位置，遇到重复数就跳过。3,2,2,1这个例子不错。

假设数组长度是5，那么数组里的元素的取值范围就是[1,5]，因此如果数组里某个元素重复了， 比如1,2,4,2,3，那么就会少一个元素，所以遇到第一个2时，我们把2放到索引1处，遇到4时把它和索引为3的元素即第二个2交换， 遇到第二个2时就不用动它，遇到3时把它和索引为2的元素即2交换。这样最终的结果为1,2,3,4,2，然后我们检查时发现索引4处的元素不等于5，这就得到重复的元素了。

class Solution {
    public List<Integer> findDuplicates(int[] nums) {
        List<Integer> res = new ArrayList<>(); // 用于存储结果的列表
        int len = nums.length; // 数组的长度
        
        // 如果数组为空，直接返回空列表
        if (len == 0) {
            return res;
        }

        // 将每个数字放到其正确的位置（索引）上
        for (int i = 0; i < len; i++) {
            // 交换的规则是每遍历一个新值，就让该值-1处的值等于该值。
            // 这样操作后，会确保出现的元素-1处的值是正确的，但是数组中是有重复元素的，
            // 所以那些缺少的元素-1处的值是不正确的，所以我们还需要遍历一次，检查出来这些位置。
            // 以3211为例，数组中只有1,2,3，所以第0,1,2处的元素是正确的，即1232，因为没有4，所以第3个位置的元素不正确，第二个for就能检查出来。
            // 如果当前数字不在其应该在的位置，并且要交换的位置的数字与当前数字不同，进行交换
            // 使用 while 而不是 if 是为了处理可能多次交换的情况。
            // 当一个数字放到其正确的位置后，新的数字可能也不在正确位置上，因此需要继续交换，直到该位置上是正确的数字。
            // 例如，如果 nums=[2,3,1]，则第一个位置需要两次交换才能变成正确的1。
            // while循环只保证当前位置的元素nums[i]在正确的位置上，不保证当前位置有正确的元素。
            // 假设数组中有两个a，则第一次遇到a时while循环会保证a在a-1处，第二次遇到a时发现a在a-1处就直接跳过了。
            // for循环结束后必有几个位置的元素不正确，这些元素就是重复元素。
            while (nums[nums[i] - 1] != nums[i]) {
                swap(nums, i, nums[i] - 1); // 交换当前位置的数字到其应该在的位置，不保证当前位置有正确的元素。
            }
        }

        // 检查每个位置上的数字，如果不在其应该在的位置上，说明是重复的
        for (int i = 0; i < len; i++) {
            if (nums[i] != i + 1) {
                res.add(nums[i]); // 记录重复的数字
            }
        }

        return res; // 返回包含所有重复数字的列表
    }

    private void swap(int[] nums, int index1, int index2) {
        if (index1 == index2) {
            return; // 如果索引相同，不需要交换
        }
        // 使用异或运算交换两个元素
        nums[index1] = nums[index1] ^ nums[index2];
        nums[index2] = nums[index1] ^ nums[index2];
        nums[index1] = nums[index1] ^ nums[index2];
    }
}

• 时间复杂度：O(n)。每一次交换操作会使得至少一个元素被交换到对应的正确位置，因此交换的次数为 O(n)，总时间复杂度为 O(n)。
• 空间复杂度：O(1)。返回值不计入空间复杂度。

a = a ^ b, b = a ^ b, a = a ^ b 这三行代码可以实现变量 a 和 b 的交换，这是因为异或操作具有一些特殊的性质。具体来说，异或操作有以下几个重要性质：

1. 自反性：x ^ x = 0
2. 零与任何数的异或等于这个数本身：x ^ 0 = x
3. 交换性：x ^ y = y ^ x
4. 结合性：x ^ (y ^ z) = (x ^ y) ^ z

基于这些性质，可以通过三个异或操作实现两个变量的交换。下面详细说明每一步的计算过程：

假设初始时 a = A，b = B。

第一步：a = a ^ b

现在 a 的值变成了 A ^ B：

• a = A ^ B
• b = B

第二步：b = a ^ b

现在 b 的值变成了 (A ^ B) ^ B，根据异或操作的自反性 x ^ x = 0 和 x ^ 0 = x，可以得到：

• b = (A ^ B) ^ B
• b = A ^ (B ^ B)
• b = A ^ 0
• b = A

此时 b 的值变成了 A：

• a = A ^ B
• b = A

第三步：a = a ^ b

现在 a 的值变成了 (A ^ B) ^ A，同样根据异或操作的性质，可以得到：

• a = (A ^ B) ^ A
• a = (A ^ A) ^ B
• a = 0 ^ B
• a = B

此时 a 的值变成了 B，而 b 的值已经变成了 A：

• a = B
• b = A