原文链接: https://leetcode-cn.com/problems/find-all-duplicates-in-an-array

英文原文

Given an integer array nums of length n where all the integers of nums are in the range [1, n] and each integer appears once or twice, return an array of all the integers that appears twice.

You must write an algorithm that runs in O(n) time and uses only constant extra space.

 

Example 1:

Input: nums = [4,3,2,7,8,2,3,1]
Output: [2,3]

Example 2:

Input: nums = [1,1,2]
Output: [1]

Example 3:

Input: nums = [1]
Output: []

 

Constraints:

• n == nums.length
• 1 <= n <= 105
• 1 <= nums[i] <= n
• Each element in nums appears once or twice.

中文题目

给定一个整数数组 a，其中1 ≤ a[i] ≤ n （n为数组长度）, 其中有些元素出现两次而其他元素出现一次。

找到所有出现两次的元素。

你可以不用到任何额外空间并在O(n)时间复杂度内解决这个问题吗？

示例：

输入:
[4,3,2,7,8,2,3,1]

输出:
[2,3]

通过代码

高赞题解

特别注意：基于“异或运算”交换两个变量的值，这种操作仅仅只是用于解题，千万不要在工作中使用这样的代码，会有一些坑，重点是：使得代码难以阅读和被他人理解。没有必要为了节约空间去牺牲代码的可读性。

---

方法：“抽屉原理” + 基于“异或运算”交换两个变量的值

思路分析：“桶排序”的思想是“抽屉原理”，即“一个萝卜一个坑”，8 个萝卜要放在 7 个坑里，则至少有 1 个坑里至少有 2 个萝卜。

“抽屉原理”的思想很简单，但是借助它我们可以完成一些比较难的问题，例如：「力扣」第 41 题：缺失的第一个正数（困难）。还有一个与本题（标注为“中等”）类似的问题：「力扣」第 448 题： 找到所有数组中消失的数字（简单），就很神奇，同样是“抽屉原理”，可以解决的问题涵盖了“简单”、“中等”、“困难”三个等级。

这里由于数组元素限定在数组长度的范围内，因此，我们可以通过一次遍历：

• 让数值 1 就放在索引位置 0 处；
• 让数值 2 就放在索引位置 1 处；
• 让数值 3 就放在索引位置 2 处；

……

一次遍历以后，那些“无处安放”的元素就是我们要找的“出现两次的元素”。

为了不使用额外的空间，这里使用到的一个技巧是“基于异或运算交换两个变量的值”：交换两个整数，除了引入一个新的变量，写出一个“轮换”的赋值表达式以外，还有两种比较 tricky 的做法，下面给出结论。

“异或运算”是不进位的二进制加法，它有如下性质：

如果 a ^ b = c ，那么 a ^ c = b 与 b ^ c = a 同时成立，利用这一条，可以用于交换两个变量的值。

于是，交换两个变量的值，例如 a 和 b，不使用第三个变量，有两种不同的方法：

基于异或运算	基于加减法
a = a ^ b b = a ^ b a = a ^ b	a = a + b b = a - b a = a - b

我理解的方式就是自己在纸上写几个例子，并且记住这个结论。个人觉得“基于异或运算”交换两个变量的值好记一些，因为右边都一样，左边依次是 a、b、a。

在这里特别感谢用户 @davidlaid 给出的意见：

• 对于异或运算实现的交换方法，如果调用 swap(nums, i, i)，那么最终的结果会变为 0。
• 对于加减法实现的交换方法，有可能发生溢出。

调用 swap(nums, i, i)，那么最终的结果会变为 0 这是因为，如果是在数组中，自己和自己交换，只有 1 个空间，这个数会在异或运算的过程中变为 0，因此单独判断一下就好了。我个人还是比价少用这个技巧的，如果题目中限制了不能使用额外的存储空间，才用“基于异或运算实现的交换方法”。

参考代码：

注意：因为这里数组的数值和索引有一个偏差，所以我将交换数组元素的方法做了一个封装，这样可以降低编码出错的概率，供大家参考。

调用 swap 方法使用了栈空间，但是如果不这么写，代码很容易出错，也不符合编码规范，我个人觉得知道这个知识点就可以了。

还是强调两点：

1、上面介绍的通过异或运算交换两个变量的做法，不要在平常工程当中用，节约不了多少空间；

2、尽量抽取方法以体现主干逻辑，尽管不符合本题意思。

写代码性能虽然很重要，但在很多时候，为了一点点性能，丢失可读性是没有必要的。

[]
import java.util.ArrayList;
import java.util.List;

public 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++) {
            while (nums[nums[i] - 1] != nums[i]) {
                swap(nums, i, nums[i] - 1);
            }
        }
        for (int i = 0; i < len; i++) {
            if (nums[i] - 1 != i) {
                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)$，这里 $N$ 是数组的长度。
• 空间复杂度：$O(1)$，这里因为使用异或运算交换数组的元素，故没有使用额外的数组空间。

统计信息

通过次数	提交次数	AC比率
46299	66362	69.8%

提交历史

提交时间	提交结果	执行时间	内存消耗	语言

相似题目

题目	难度
找到所有数组中消失的数字	简单