在数组中查找重复的数字

I am debugging below problem and post the solution I am debugging and working on, the solution or similar is posted on a couple of forums, but I think the solution has a bug when num[0] = 0 or in general num[x] = x? Am I correct? Please feel free to correct me if I am wrong.

我在问题下面调试并发布我正在调试和处理的解决方案，解决方案或类似的方案被发布在一些论坛上，但是我认为解决方案在num[0] = 0或通常num[x] = x时存在bug ?我正确吗?如果我说错了，请随时纠正。

Given an array nums containing n + 1 integers where each integer is between 1 and n (inclusive), prove that at least one duplicate number must exist. Assume that there is only one duplicate number, find the duplicate one.

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

Note: You must not modify the array (assume the array is read only). You must use only constant, O(1) extra space. Your runtime complexity should be less than O(n2). There is only one duplicate number in the array, but it could be repeated more than once.

注意:您不能修改数组(假设数组是只读的)。你必须使用常数，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;
}

4 个解决方案

#1

1. Start with two pointers to the first element: fast and slow.
2. 从两个指向第一个元素的指针开始:快速和缓慢。
3. Define a 'move' as incrementing fast by 2 step(positions) and slow by 1.
4. 将“移动”定义为快速增加2步(位置)，慢增加1步。
5. After each move, check if slow & fast point to the same node.
6. 每次移动后，检查是否慢速指向相同的节点。
7. If there is a loop, at some point they will. This is because after they are both in the loop, fast is moving twice as quickly as slow and will eventually 'run into' it.
8. 如果有一个循环，在某个时候他们会。这是因为在两者都在循环之后，fast的移动速度是slow的两倍，并且最终会“撞到”它。
9. Say they meet after k moves. This is NOT NECESSARILY the repeated element, since it might not be the first element of the loop reached from outside the loop.
   Call this element X.
10. 假设它们在k移动后相遇。这不一定是重复元素，因为它可能不是从循环外部到达的循环的第一个元素。调用这个元素X。
11. Notice that fast has stepped 2k times, and slow has stepped k times.
12. 请注意，fast已经走了2k次，并且慢的已经走了k次。
13. Move fast back to zero.
14. 快速回到0。
15. Repeatedly advance fast and slow by ONE STEP EACH, comparing after each step.
16. 反复前进，每一步都快一步，每一步都慢一步，每一步都比一步。
17. Notice that after another k steps, slow will have moved a total of 2k steps and fast a total of k steps from the start, so they will again both be pointing to X.
18. 注意，在另一个k步之后，slow会移动总共2k步，而fast从一开始就是k步，所以它们都指向X。
19. Notice that if the prior step is on the loop for both of them, they were both pointing to X-1. If the prior step was only on the loop for slow, then they were pointing to different elements.
20. 注意，如果前面的步骤在循环中，它们都指向X-1。如果前面的步骤只是在循环中缓慢进行，那么它们指向不同的元素。
21. Ditto for X-2, X-3, ...
22. X-2, X-3，…
23. So in going forward, the first time they are pointing to the same element is the first element of the cycle reached from outside the cycle, which is the repeated element you're looking for.
24. 所以在以后，第一次他们指向相同的元素时，是在循环之外到达的第一个元素，也就是你要寻找的重复元素。

#2

Below is my code which uses Floyd's cycle-finding algorithm:

下面是我的代码，使用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;
}

Comment This works because zeroes aren't allowed, so the first element of the array isn't part of a cycle, and so the first element of the first cycle we find is referred to both outside and inside the cycle. If zeroes were allowed, this would fail if arr[0] were on a cycle. E.g., [0,1,1].

注释这个工作是因为0是不允许的，所以数组的第一个元素不是循环的一部分，所以我们发现的第一个循环的第一个元素是在循环的外部和内部。如果允许0，那么如果arr[0]在一个循环中，这将失败。例如,(0,1,1)。

#3

The sum of integers from 1 to N = (N * (N + 1)) / 2. You can use this to find the duplicate -- sum the integers in the array, then subtract the above formula from the sum. That's the duplicate.

从1到N的整数的和= (N * (N + 1)) / 2。您可以使用它来查找重复的——对数组中的整数求和，然后从求和中减去上面的公式。这是重复的。

Update: The above solution is based on the (possibly invalid) assumption that the input array consists of the values from 1 to N plus a single duplicate.

更新:上面的解决方案基于(可能无效)的假设，即输入数组包含从1到N的值加上单个副本。

#4

Since you cannot use any additional space, using another hash table would be ruled out.

由于不能使用任何其他空间，因此将不使用其他哈希表。

Now, coming to the approach of hashing on existing array, it can be acheived if we are allowed to modify the array in place.

现在，谈到对现有数组进行散列处理的方法，如果允许我们对数组进行适当的修改，就可以实现这一点。

Algo:

算法:

1) Start with the first element.

1)从第一个元素开始。

2) Hash the first element and apply a transformation to the value of hash.Let's say this transformation is making the value -ve.

2)哈希第一个元素并对哈希值应用一个转换。假设这个变换使值为-ve。

3)Proceed to next element.Hash the element and before applying the transformation, check if a transformation has already been applied.

3)继续下一个元素。哈希元素，在应用转换之前，检查是否已经应用了转换。

4) If yes, then element is a duplicate.

4)如果是，则元素是重复的。

Code:

代码:

 for(i = 0; i < size; i++)
  {
    if(arr[abs(arr[i])] > 0)
      arr[abs(arr[i])] = -arr[abs(arr[i])];
    else
      cout<< abs(arr[i]) <<endl;
  }  

This transformation is required since if we are to use hashing approach,then, there has to be a collision for hashing the same key.

这种转换是必需的，因为如果我们要使用散列方法，那么就必须有一个冲突来哈希相同的键。

I cant think of a way in which hashing can be used without any additional space and not modifying the array.

我想不出一种不用任何额外空间和不修改数组就可以使用散列的方法。