HHot 100C++ 图解

287. 寻找重复数

一句话套路值当下一跳构成链表 → Floyd 找环入口

题目描述

给定一个包含 n + 1 个整数的数组 nums ,其数字都在 [1, n] 范围内(包括 1 和 n),可知至少存在一个重复的整数。

假设 nums 只有 一个重复的整数 ,返回 这个重复的数 。

你设计的解决方案必须 不修改 数组 nums 且只用常量级 O(1) 的额外空间。

 

示例 1:

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

示例 2:

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

示例 3 :

输入:nums = [3,3,3,3,3]
输出:3

 

 

提示:

  • 1 <= n <= 105
  • nums.length == n + 1
  • 1 <= nums[i] <= n
  • nums 中 只有一个整数 出现 两次或多次 ,其余整数均只出现 一次

 

进阶:

  • 如何证明 nums 中至少存在一个重复的数字?
  • 你可以设计一个线性级时间复杂度 O(n) 的解决方案吗?

思路

时间O(n)、空间 O(1)(最优)
空间O(1)(最优)

约束

不能修改数组、只能用 O(1) 额外空间 —— 排序/哈希/set 全部出局。

思路 A(Floyd 判圈)

把下标当结点、nums[i] 当「下一条边」,n+1 个数落在 [1,n],所以一定有环;重复的数就是环的入口。

快慢指针

slow=nums[slow],fast=nums[nums[fast]];

相遇后把一个放回起点,各走一步,再相遇处即入口(Q142 同款)。

思路 B(值域二分)

对值 mid 统计「<= mid 的元素个数」,个数 > mid 说明重复值在左半边。

O(n log n),不需要修改数组,也很好想。

思路 C(原地取负)

把 nums[x] 位置的数取负当 visited —— 但违反「不修改数组」。

图解

4 0 1 1 8 2 8 3 7 4 5 5 2 6 6 7 3 8
数组(来自本仓库测试数据,下标从 0 开始)

逐帧动画

1 / 3

快捷键:← → 单步,空格播放 / 暂停。

C++17 题解

src/17_tricks.cpp34 行
namespace lc0287 {
class Solution {
 public:
  static int findDuplicate(vector<int>& nums) {
    int slow = nums[0], fast = nums[nums[0]];
    while (slow != fast) {  // 阶段一:找相遇点
      slow = nums[slow];
      fast = nums[nums[fast]];
    }
    slow = 0;  // 阶段二:一个回起点,同速前进(Q142 的结论)
    while (slow != fast) {
      slow = nums[slow];
      fast = nums[fast];
    }
    return slow;
  }

  // 值域二分版:不依赖「慢指针能到起点」这个性质,思路更直白
  static int findDuplicateBinary(vector<int>& nums) {
    int lo = 1, hi = (int)nums.size() - 1;  // 值域是 [1, n]
    while (lo < hi) {
      int mid = lo + (hi - lo) / 2;
      int cnt = 0;
      for (int x : nums)
        if (x <= mid) ++cnt;  // 统计 <= mid 的元素个数
      if (cnt > mid)
        hi = mid;  // 抽屉原理:重复值在 [lo, mid]
      else
        lo = mid + 1;
    }
    return lo;
  }
};
}

单元测试

以下用例都在本仓库里实际编译运行过,图解里的数据也取自这里。

TEST q287_find_the_duplicate_number22 行
lc0287::Solution s;
vector<int> a{1, 3, 4, 2, 2};
CHECK_EQ(s.findDuplicate(a), 2);
CHECK_EQ(s.findDuplicateBinary(a), 2);
vector<int> b{3, 1, 3, 4, 2};
CHECK_EQ(s.findDuplicate(b), 3);
CHECK_EQ(s.findDuplicateBinary(b), 3);
vector<int> c{1, 1};
CHECK_EQ(s.findDuplicate(c), 1);
CHECK_EQ(s.findDuplicateBinary(c), 1);
vector<int> d{2, 2, 2, 2, 2};  // 只有一种数且重复多次
CHECK_EQ(s.findDuplicate(d), 2);
CHECK_EQ(s.findDuplicateBinary(d), 2);
vector<int> e{1, 4, 4, 2, 3};  // 长度为 n+1 时元素必须落在 [1,n](否则下面的快指针会越界)
CHECK_EQ(s.findDuplicate(e), 4);
CHECK_EQ(s.findDuplicateBinary(e), 4);
vector<int> f{1, 2, 3, 4, 5, 6, 6};  // 6 出现两次
CHECK_EQ(s.findDuplicate(f), 6);
CHECK_EQ(s.findDuplicateBinary(f), 6);
// 两版必须完全一致(Floyd 依赖「从 0 出发进环」,二分版不依赖)
vector<int> g{4, 1, 8, 8, 7, 5, 2, 6, 3};
CHECK_EQ(s.findDuplicate(g), s.findDuplicateBinary(g));

↑↓ 选择↵ 打开/ 随时唤起