大家好，我是 @负雪明烛。👈👈 点击关注，优质题解不间断。

题目大意

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

条件：

  • 数组长度是 442. 数组中重复的数据 - 图1，每个数据的取值范围是 442. 数组中重复的数据 - 图2
  • 每个数字只出现一次或者两次
  • 要求时间复杂度 $O(N)$，空间复杂度是 $O(1)$

解题方法

原地修改数组

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

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

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

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

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

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

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

  • 数组长度是 442. 数组中重复的数据 - 图3，每个数据的取值范围是 442. 数组中重复的数据 - 图4

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

本题中，数组中数字的取值范围 442. 数组中重复的数据 - 图5，正好与下标的范围 442. 数组中重复的数据 - 图6对应。

因此，就有一个思路，对于 nums[i] ，我们将下标 442. 数组中重复的数据 - 图7的位置的数字进行映射（还要能映射回去）。

映射方法通常有两种：

  • 取反
  • 增加偏移量

方法一：取反

  • 从起始位置进行遍历，每次将下标为 442. 数组中重复的数据 - 图8的数字取反；
  • 当遍历到 442. 数组中重复的数据 - 图9为负数，需要忽略其负号。
  • 若发现下标为 442. 数组中重复的数据 - 图10的数字已经是负数，说明之前出现过同样的数字 442. 数组中重复的数据 - 图11，即找到了重复数字；

动画图解如下：

代码如下：

  1. class Solution(object):
  2.     def findDuplicates(self, nums):
  3.         """
  4.         :type nums: List[int]
  5.         :rtype: List[int]
  6.         """
  7.         ans = []
  8.         for num in nums:
  9.             if nums[abs(num) - 1] < 0:
  10.                 ans.append(abs(num))
  11.             nums[abs(num) - 1] *= - 1
  12.         return ans
  1. class Solution {
  2. public:
  3.     vector<int> findDuplicates(vector<int>& nums) {
  4.         const int N = nums.size();
  5.         vector<int> res;
  6.         for (int i = 0; i < N; i++) {
  7.             if (nums[abs(nums[i]) - 1] < 0)
  8.                 res.push_back(abs(nums[i]));
  9.             nums[abs(nums[i]) - 1] *= -1;
  10.         }
  11.         return res;
  12.     }
  13. };

方法二：增加偏移量

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

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

比如，本题中数字的范围是 442. 数组中重复的数据 - 图12，我们可以增加一个偏移量 442. 数组中重复的数据 - 图13，即映射到了一个新的数组空间。

做法：

  • 从起始位置进行遍历，每次将下标为 442. 数组中重复的数据 - 图14的数字 442. 数组中重复的数据 - 图15；
  • 遍历到 442. 数组中重复的数据 - 图16超过 442. 数组中重复的数据 - 图17，需要忽略将其 442. 数组中重复的数据 - 图18恢复原值；
  • 若发现下标为 442. 数组中重复的数据 - 图19的数字已经是超过 442. 数组中重复的数据 - 图20，说明之前出现过同样的数字 442. 数组中重复的数据 - 图21，即找到了重复数字；

代码如下：

  1. class Solution {
  2. public:
  3.     vector<int> findDuplicates(vector<int>& nums) {
  4.         vector<int> res;
  5.         for (int num : nums) {
  6.             if (nums[(num % 100000) - 1] > 100000) {
  7.                 res.push_back(num % 100000);
  8.             }
  9.             nums[(num % 100000) - 1] += 100000;
  10.         }
  11.         return res;
  12.     }
  13. };

复杂度

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

    总结

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

我是 @负雪明烛 ，刷算法题 1000 多道，写了 1000 多篇算法题解，收获阅读量 300 万。
关注我，你将不会错过我的精彩动画题解、面试题分享、组队刷题活动，进入主页 @负雪明烛 右侧有刷题组织，从此刷题不再孤单。