关键词：LeetCode，力扣，题解，算法，算法题，解析，C++, Java, Python，数组，重复数字，442

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

题目描述

给你一个长度为 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∗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

1 2 3 4 5 6 7 8

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;
    }
};

1 2 3 4 5 6 7 8 9 10 11 12 13

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 2 3 4 5 6 7 8 9 10 11 12 13

方法二：增加偏移量

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

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

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

做法：

• 从起始位置进行遍历，每次将下标为 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

1 2 3 4 5 6 7 8 9

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;
    }
};

1 2 3 4 5 6 7 8 9 10 11 12 13

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;
    }
}

1 2 3 4 5 6 7 8 9 10 11 12 13

复杂度

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

总结

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

DDKK.COM 弟弟快看-教程，程序员编程资料站，版权归原作者所有

本文经作者：负雪明烛 授权发布，任何组织或个人未经作者授权不得转发