442. Find All Duplicates in an Array 数组中重复的数据

• 作者： 负雪明烛
• id： fuxuemingzhu
• 个人博客： http://fuxuemingzhu.cn/
• 关键词：LeetCode，力扣，题解，算法，算法题，解析，C++, Java, Python，数组，重复数字，442

---

@TOC

题目地址：https://leetcode-cn.com/problems/find-all-duplicates-in-an-array/

题目描述

给你一个长度为 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]
输出：[]

提示：

1. n == nums.length
2. 1 <= n <= 10^5
3. 1 <= nums[i] <= n
4. nums 中的每个元素出现 一次 或 两次

题目大意

题目让找出数组中出现两次的数字。要求时间复杂度是 $O(N)$，空间复杂度是 $O(1)$。

条件：

• 数组长度是 $n$，每个数据的取值范围是 $[1,n]$
• 每个数字只出现一次或者两次
• 要求时间复杂度 $O(N)$，空间复杂度是 $O(1)$

解题方法

原地修改数组

遇到这个题，你的第一思路是什么呢？

我想一定是使用 set 或者 hashmap保存已经出现过的数字、或者数字出现的次数。

但这就不符合题目的空间复杂度是 $O(1)$，即不使用额外空间的限制条件。

我的第二个思路是对数组排序，排序后相同的数字会相邻。可是排序的时间复杂度是 $O(N\ast log(N))$不符合题目的时间复杂度$O(N)$。

所以，只能祭出大杀器：「原地修改数组」了。

其实这个思路是沿着 hashmap的思路演化出来的，只要遇到过一次就学会了。

我们注意题目给出的条件：

• 数组长度是 $n$，每个数据的取值范围是 $[1,n]$

我们知道一个数组有 下标和 值两个概念，根据下标获取到值。

本题中，数组中数字的取值范围 $[1,n]$，正好与下标的范围 $[0,n-1]$对应。

因此，就有一个思路，对于 nums[i] ，我们将下标 $=nums[i]-1$的位置的数字进行映射（还要能映射回去）。

映射方法通常有两种：

• 取反
• 增加偏移量

方法一：取反

• 从起始位置进行遍历，每次将下标为 $nums[i]-1$的数字取反；
• 当遍历到值 $nums[i]$ 为负数，需要忽略其负号。
• 若发现下标为 $nums[i]-1$的数字已经是负数，说明之前出现过同样的数字 $nums[i]$，即找到了重复数字；

动画图解如下：

对应的图如下，可以逐一观看：

Python 语言的代码如下：

class Solution(object):
    def findDuplicates(self, nums):
        ans = []
        for num in nums:
            if nums[abs(num) - 1] < 0:
                ans.append(abs(num))
            nums[abs(num) - 1] *= - 1
        return ans

C++ 语言的代码如下：

class Solution {
public:
    vector<int> findDuplicates(vector<int>& nums) {
        const int N = nums.size();
        vector<int> res;
        for (int i = 0; i < N; i++) {
            if (nums[abs(nums[i]) - 1] < 0)
                res.push_back(abs(nums[i]));
            nums[abs(nums[i]) - 1] *= -1;
        }
        return res;
    }
};

Java 语言的代码如下：

class Solution {
    public List<Integer> findDuplicates(int[] nums) {
        List<Integer> res = new ArrayList<>();
        for (int num : nums) {
            if (nums[Math.abs(num) - 1] < 0) {
                res.add(Math.abs(num));
            } else {
                nums[Math.abs(num) - 1] *= -1;
            }
        }
        return res;
    }
}

方法二：增加偏移量

除了取反之外，我们还可以增加一个偏移量，只要映射后与原数组的范围区分开就行。

思路和取反一样，只是为了映射后与映射前的数组不混淆。

比如，本题中数字的范围是 $[1,10^5]$，我们可以增加一个偏移量 $10^5$，即映射到了一个新的数组空间。

做法：

• 从起始位置进行遍历，每次将下标为 $nums[i]-1$的数字 $+100000$；
• 遍历到值 $nums[i]$超过 $100000$，需要将其 $-100000$ 恢复原值；
• 若发现下标为 $nums[i]-1$ 的数字已经超过 $100000$，说明之前出现过同样的数字 $nums[i]$，即找到了重复数字；

Python 语言的代码如下：

class Solution(object):
    def findDuplicates(self, nums):
        res = []
        for num in nums:
            if nums[(num % 100000) - 1] > 100000:
                res.append(num % 100000)
            else:
                nums[(num % 100000) - 1] += 100000
        return res

C++ 语言的代码如下：

class Solution {
public:
    vector<int> findDuplicates(vector<int>& nums) {
        vector<int> res;
        for (int num : nums) {
            if (nums[(num % 100000) - 1] > 100000) {
                res.push_back(num % 100000);
            }
            nums[(num % 100000) - 1] += 100000;
        }
        return res;
    }
};

Java 语言的代码如下：

class Solution {
    public List<Integer> findDuplicates(int[] nums) {
        List<Integer> res = new ArrayList<>();
        for (int num : nums) {
            if (nums[(num % 100000) - 1] > 100000) {
                res.add(num % 100000);
            } else {
                nums[(num % 100000) - 1] += 100000;
            }
        }
        return res;
    }
}

复杂度

• 时间复杂度：$O(N)$
• 空间复杂度：$O(1)$

总结

1. 这个题是技巧题目，看懂了我的题解以后，以后遇到同样的题目，应该就会了。

日期

2018 年 2 月 6 日 2018 年 12 月 5 日 —— 周三啦！ 2022 年 5 月 8 日 —— 五一调休后，本周末只有一天休息