在数组中找到重复的数字

Question

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

给定包含n + 1个整数的数组nums,其中每个整数在1和n之间(包括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].

Answer 2

1. 从指向第一个元素的两个指针开始：fast和Slow。
2. 将“移动”定义为快增量2 步（位置），慢增量 1。
3. 每次移动后，检查慢速和快速是否指向同一节点。
4. 如果存在循环，在某些时候它们就会出现。这是因为当它们都进入循环后，快的移动速度是慢的两倍，并且最终会“遇到”它。
5. 假设他们在k 步之后相遇。这不一定是重复元素，因为它可能不是从循环外部到达的循环的第一个元素。
   将此元素称为X。
6. 请注意，fast已步进2k次，slow已步进k次。
7. 快速回到零。
8. 反复快、慢各一步前进，每一步后进行比较。
9. 请注意，再过k步后，slow 将总共移动2k步，fast将从开始总共移动k步，因此它们将再次指向X。
10. 请注意，如果前一步都在循环中，则它们都指向X-1。如果前面的步骤仅在Slow循环中，那么它们就指向不同的元素。
11. X-2、X-3、 ...也是如此
12. 因此，在接下来的过程中，它们第一次指向同一元素是从循环外部到达的循环的第一个元素，这就是您要查找的重复元素。