287寻找重复数（Floyd判圈算法、二分查找）_弗洛伊德判环那个重复的数是什么

1、题目描述

给定一个包含 n + 1 个整数的数组 nums，其数字都在 1 到 n 之间（包括 1 和 n），可知至少存在一个重复的整数。假设只有一个重复的整数，找出这个重复的数。

说明：

• 不能更改原数组（假设数组是只读的）。
• 只能使用额外的 O(1) 的空间。
• 时间复杂度小于 O(n2) 。
• 数组中只有一个重复的数字，但它可能不止重复出现一次。

2、示例

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

3、题解

解法一：

基本思想：快慢指针，Floyd判圈算法，时间复杂度O(n)空间复杂度O(1)

假设环长为 L，从起点到环的入口的步数是 a，从环的入口继续走 b 步到达相遇位置，从相遇位置继续走 c 步回到环的入口，则有 b+c=L，其中 L、a、b、c 都是正整数。根据上述定义，慢指针走了 a+b 步，快指针走了 2(a+b) 步。从另一个角度考虑，在相遇位置，快指针比慢指针多走了若干圈，因此快指针走的步数还可以表示成 a+b+kL，其中 kk表示快指针在环上走的圈数。联立等式，可以得到：2(a+b)=a+b+kL

解得 a=kL-b，整理可得：a=(k-1)L+(L-b)=(k-1)L+c

从上述等式可知，如果慢指针从起点出发，快指针从相遇位置出发，每次两个指针都移动一步，则慢指针走了 a 步之后到达环的入口，快指针在环里走了 k-1 圈之后又走了 c 步，由于从相遇位置继续走 c 步即可回到环的入口，因此快指针也到达环的入口。两个指针在环的入口相遇，相遇点就是答案。

解法二：

基本思想：二分查找，时间复杂度O(nlongn)空间复杂度O(1)
        arr = [1,3,4,2,2] 此时数字在 1 — 5 之间
        mid = (1 + 5) / 2 = 3 arr小于等于的3有4个(1,2,2,3)，1到3中肯定有重复的值
        mid = (1 + 3) / 2 = 2 arr小于等于的2有3个(1,2,2)，1到2中肯定有重复的值
        mid = (1 + 2) / 2 = 1 arr小于等于的1有1个(1)，2到2中肯定有重复的值
        所以重复的数是 2

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
class Solution {
public:
    int findDuplicate(vector<int>& nums) {
        //基本思想：快慢指针，Floyd判圈算法，时间复杂度O(n)空间复杂度O(1)
        int slow=0,fast=0;
        while(true)
        {
            slow=nums[slow];
            fast=nums[nums[fast]];
            if(slow==fast)
                break;
        }
        slow=0;
        while(slow!=fast)
        {
            slow=nums[slow];
            fast=nums[fast];
        }
        return fast;
    }
};
class Solution1 {
public:
    int findDuplicate(vector<int>& nums) {
        //基本思想：二分查找
        /*
        arr = [1,3,4,2,2] 此时数字在 1 — 5 之间
        mid = (1 + 5) / 2 = 3 arr小于等于的3有4个(1,2,2,3)，1到3中肯定有重复的值
        mid = (1 + 3) / 2 = 2 arr小于等于的2有3个(1,2,2)，1到2中肯定有重复的值
        mid = (1 + 2) / 2 = 1 arr小于等于的1有1个(1)，2到2中肯定有重复的值
        所以重复的数是 2
        */
        int n = nums.size();
        int l = 1, r = n - 1, res;
        while (l <= r) {
            int mid = l +(r - l)/2;
            int cnt = 0;
            for (int i = 0; i < n; ++i) {
                if(nums[i] <= mid)
                    cnt++;
            }
            if (cnt <= mid) {
                l = mid + 1;
            } else {
                r = mid - 1;
                res = mid;
            }
        }
        return res;
    }
};
int main()
{
    Solution solute;
    vector<int> nums={1,3,4,2,2};
    cout<<solute.findDuplicate(nums)<<endl;
    return 0;
}