查找数组中的重复数字

Question

我正在调试下面的问题，post 我正在调试和研究的解决方案，解决方案或类似的解决方案在几个论坛上 posted，但我认为该解决方案有一个错误当 num[0] = 0 或一般情况下 num[x] = x？我对么？如有不妥欢迎指正

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

注意：您不得修改数组（假设数组是只读的）。您必须只使用常量，O(1) extra space。您的运行时复杂度应小于 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

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

Update：上述解决方案基于（可能无效的）假设，即输入数组由 1 到 N 的值加上一个重复值组成。

Answer 2

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

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

Answer 3

因为您不能使用任何额外的 space，使用另一个散列 table 将被排除。

现在，谈到对现有数组进行散列的方法，如果允许我们就地修改数组，就可以实现。

Algo:

1) 从第一个元素开始。

2) 对第一个元素进行哈希处理并对 hash.Let 的值应用转换，假设此转换使值成为 -ve。

3)继续下一个 element.Hash 元素，在应用转换之前，检查是否已应用转换。

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

代码：

 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;
  }

这种转换是必需的，因为如果我们要使用散列方法，那么对相同的密钥进行散列就必须发生冲突。

我想不出一种无需任何额外 space 且无需修改数组即可使用散列的方法。

Answer 4

从指向第一个元素的两个指针开始：fast 和 slow。
将 'move' 定义为递增 fast 2 步（位置）和 slow 递增 1.
每次移动后，检查slow & fast是否指向同一个节点。
如果有循环，在某个时候他们会的。这是因为在它们都进入循环后，fast 的移动速度是 slow 的两倍，并且最终会 'run into'。
假设他们在 k 步后相遇。这不一定是重复元素，因为它可能不是从循环外部到达的循环的第一个元素。
调用此元素 X.
注意fast步进了2k次，slow步进了k次。
将快速移回零。
重复fast和slow一步一步，每一步比较。
请注意，在另一个 k 步之后，慢速将总共移动 2k 步，而 fast 从一开始总共 k 步，因此它们将再次指向 X.
请注意，如果前面的步骤都在循环中，则它们都指向 X-1。如果前面的步骤仅在 slow 的循环中，那么它们指向不同的元素。
同上 X-2、X-3、 ...
所以在前进中，它们第一次指向同一个元素是从循环外到达的循环的第一个元素，也就是您要查找的重复元素。

查找数组中的重复数字

find duplicate number in an array

c++

algorithm

find