leetcode：287. 寻找重复数

题目

给定一个包含 n + 1 个整数的数组 nums ，其数字都在 [1, n] 范围内（包括 1 和 n），可知至少存在一个重复的整数。
假设 nums 只有 一个重复的整数（即只有一个整数出现两次或多次 ，其余整数均只出现一次） ，返回 这个重复的数 。
你设计的解决方案必须 不修改 数组 nums 且只用常量级 O(1) 的额外空间。

示例：

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

进阶：你可以设计一个线性级时间复杂度 O(n) 的解决方案吗？

解答 & 代码

解法 0：原地哈希

该解法不合题意，因为题目要求不修改数组 **nums**

让数组 nums 变成一个“哈希表”：

  • 下标 idx 对应的元素 nums[idx] 如果是负数，则说明 idx 这个数字已经存在；

  • 否则，如果下标 idx 对应的元素 nums[idx] 是正数，则说明 idx 这个数字不存在

    1. class Solution {
    2. public:
    3.   int findDuplicate(vector<int>& nums) {
    4.       for(int i = 0; i < nums.size(); ++i)
    5.       {
    6.           int num = abs(nums[i]);
    7.           // 如果哈希表中 num 这个数已存在，则 num 是重复数，直接返回
    8.           if(nums[num] < 0)
    9.               return num;
    10.           // 如果哈希表中 num 这个数不存在，则插入（将对应的元素置为负数）
    11.           else
    12.               nums[num] = -nums[num];
    13.       }
    14.       return -1;
    15.   }
    16. };

    复杂度分析：

  • 时间复杂度 O(n)

  • 空间复杂度 O(1)

执行结果：

  1. 执行结果：通过
  3. 执行用时：84 ms, 在所有 C++ 提交中击败了 78.48% 的用户
  4. 内存消耗：59.7 MB, 在所有 C++ 提交中击败了 79.69% 的用户

解法一：快慢指针

参考环形链表寻找入环节点的做法：
[中等] 142. 环形链表 II

对 nums 数组建图，每个位置 i 的 next 节点位置为 nums[i]，得到一个环形链表（因为重复数字 target 至少出现两次，因此至少有两个节点都指向下标为 target 的节点，因此图中一定存在环）
image.png
入环节点的下标就是重复的数。

  1. class Solution {
  2. public:
  3.     int findDuplicate(vector<int>& nums) {
  4.         int fast = 0;    // 快指针
  5.         int slow = 0;    // 慢指针
  6.         while(fast != nums.size() && nums[fast] != nums.size())
  7.         {
  8.             fast = nums[nums[fast]];
  9.             slow = nums[slow];
  10.             if(fast == slow)
  11.                 break;
  12.         }
  13.         fast = 0;
  14.         while(fast != slow)
  15.         {
  16.             fast = nums[fast];
  17.             slow = nums[slow];
  18.         }
  19.         return fast;    // 入环节点的下标就是重复数字
  20.     }
  21. };

复杂度分析：

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

执行结果：

  1. 执行结果：通过
  3. 执行用时：80 ms, 在所有 C++ 提交中击败了 87.16% 的用户
  4. 内存消耗：59.7 MB, 在所有 C++ 提交中击败了 71.85% 的用户