c++ - 查找数组中的重复数字

Question

我正在调试下面的问题并发布我正在调试和处理的解决方案，解决方案或类似的解决方案发布在几个论坛上，但我认为当 num[0] = 0 或一般 num [x] = x?我对么？如果我错了，请随时纠正我。

给定一个包含 n + 1 个整数的数组 nums，其中每个整数都介于 1 和 n(含)之间，证明至少必须存在一个重复数字。假设只有一个重复的数字，找到重复的那个。

注意: 您不得修改数组(假设数组是只读的)。 您必须仅使用常量 O(1) 额外空间。 您的运行时复杂度应小于 O(n2)。 数组中只有一个重复的数字，但可以重复多次。

int findDuplicate3(vector<int>& nums)
{
    if (nums.size() > 1)
    {
        int slow = nums[0];
        int fast = nums[nums[0]];
        while (slow != fast)
        {
            slow = nums[slow];
            fast = nums[nums[fast]];
        }

        fast = 0;
        while (fast != slow)
        {
            fast = nums[fast];
            slow = nums[slow];
        }
        return slow;
    }
    return -1;
}

Answer 1

下面是我的代码，它使用了 Floyd 的循环查找算法:

#include <iostream>
#include <vector>
using namespace std;

int findDup(vector<int>&arr){
    int len = arr.size();
    if(len>1){
        int slow = arr[0];
        int fast = arr[arr[0]];
        while(slow!=fast){
            slow = arr[slow];
            fast = arr[arr[fast]];
        }
        fast = 0;
        while(slow!=fast){
            slow = arr[slow];
            fast = arr[fast];
        }
        return slow;
    }
    return -1;
}

int main() {
    vector<int>v = {1,2,2,3,4};
    cout<<findDup(v)<<endl;
    return 0;
}

评论 这是有效的，因为不允许零，所以数组的第一个元素不是循环的一部分，所以我们找到的第一个循环的第一个元素都被引用外循环和内循环。如果允许零，则如果 arr[0] 处于循环中，这将失败。例如，[0,1,1]。