时间轴

2026-03-17

init

题目：

P287 寻找重复数

https://leetcode.cn/problems/find-the-duplicate-number/description/?envType=study-plan-v2&envId=top-100-liked

鸽巢原理（也叫抽屉原理，英文 Pigeonhole Principle）是组合数学里一个非常基础但很强大的原理。

基本思想: 如果 n + 1 只鸽子放进 n 个鸽巢, 那么至少有一个鸽巢里有 ≥2 只鸽子

这个题利用 Floyd 判圈法，转换成 P142 这种问题

P142 环形链表 II

https://even629.com/posts/142

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
#include <vector>
using std::vector;

class Solution {
    public:
        int findDuplicate(vector<int> &nums)
        {
                // 1 <= n <= 105
                // nums.length == n + 1
                // 1 <= nums[i] <= n
                // nums 中 只有一个整数 出现 两次或多次 ，其余整数均只出现 一次

                int slow = 0, fast = 0;

                do {
                        slow = nums[slow];
                        fast = nums[nums[fast]];
                } while (slow != fast);
                // 相遇
                slow = 0;
                do {
                        slow = nums[slow];
                        fast = nums[fast];
                } while (slow != fast);

                return slow;
        }
};