寻找重复数

题目 寻找重复数

image-783dd323

思路分析

没必要 但可以用这个快慢指针构造环路去做

image-e78ab977

在值和下标间构建一条边 下标和值间再构建一条边

如果有重复的数 就肯定会有俩个值指向同一个下标的边

从而形成回路

这个回路就是入口 就是我们要找的重复的数

代码实现

class Solution {

public:

    int findDuplicate(vector<int>& nums) {

        int slow=0,fast=0;

        do{

            slow=nums[slow];

            fast=nums[nums[fast]];

        }while(slow!=fast);

        slow=0

        while(slow!=fast)

        {

            slow=nums[slow];

            fast=nums[fast];

        }

        return slow;

    }

};

同类题型

视频讲解

⬅️ 共享 🏠 00-刷题理模型 ➡️ 快慢指针