在数组中查找重复的数字

Question

在数组中查找重复的数字

9

我正在调试下面的问题，并发布解决方案。这个问题已经在几个论坛上发帖了，但是当num[0] = 0或者一般情况下num[x] = x时，我认为解决方案存在一个bug，这种情况下请纠正我。

给定一个包含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;
}

- Lin Ma

2

这个算法基本上不起作用，而 x[i]=i 只是其中较小的问题。更大的问题是它永远不会看到 [1,2,3,0,4,4] 中的重复项。 - n. m.

1

当 arr[i] == i 时，有两种可能性，即 arr[i] 是重复项，则没有问题，上述算法将正常工作。第二种可能性是 arr[i] == i 且 arr[i] 不是重复项（假设 i 是非零的，我们可以单独处理该情况），那么我的观点是你永远不会通过上述算法到达位置 i。如果您认为有任何错误，请提供反例。（再次强调 i==0 的情况要单独处理），因为我不知道如何正式表达它。 - Khatri

1

@n.m. 最初慢指针=4，快指针=2，在下一次迭代中，慢指针=2，快指针=2，然后第一个 while 循环中断，然后您将快指针设置为 arr[0]，即 4，并将两个指针向前移动一步，即慢指针=3，快指针=4，下一次迭代慢指针=2，快指针=2，这样就找到了重复的元素。 - Khatri

1

@n.m. 但问题说数组的元素在1到n的范围内，而你却包括了0。这个算法的假设是相同的，如果不满足这个条件，那么毫无疑问，你至少不能直接应用这个算法。 - Khatri

3

问题中似乎存在内部矛盾，因为它说 x[0]==0 是一个问题，所以我认为0是允许的。如果不是这样的话，那么算法可能就没问题了。 - n. m.

显示剩余13条评论

4个回答

3

从1加到N的整数之和 = (N * (N + 1)) / 2。您可以使用此公式找到重复项 - 对数组中的整数求和，然后从总和中减去上述公式。这就是重复项。

更新：上述解决方案基于这样一个（可能无效的）假设：输入数组由从1到N的值和单个重复值组成。

- keithmo

非常聪明，Keithmo，但是你如何证明有重复？ - Lin Ma

1

数组中只有一个重复的数字，但它可能会重复多次。但这个想法很棒。 - Roman Pustylnikov

1

哎呀，我错过了“重复多次”的部分。我的错。 - keithmo

嗨，keithmo，我认为你是正确的，只有一个重复的数字。问题本身存在问题。 - Lin Ma

1

我认为所描述的问题可能允许例如N = 5和数组= [1, 1, 5, 1, 1, 2]。如果是这样，那么我的解决方案将会非常失败。 - keithmo

@keithmo，我认为你上面的情况不存在，因为它不是N个不同的数字在N+1个插槽中。 :) - Lin Ma

1

将两个指针指向第一个元素：fast和slow。
定义“移动”为将fast递增2步（位置），将slow递增1步。
每次move后，检查slow和fast是否指向同一个节点。
如果有循环，它们在某个时刻将会相遇。这是因为当它们都在循环中时，fast的移动速度是slow的两倍，并最终“撞上”它。
假设它们在k moves后相遇。这不一定是重复的元素，因为它可能不是从循环外部到达的第一个元素。
称此元素为X。
请注意，fast已经移动了2k次，而slow只移动了k次。
将fast移回零。
重复地使fast和slow每次移动一步，每次比较。
请注意，在另外k步之后，慢指针总共移动了2k步，而快指针总共移动了从开始算起的k步，因此它们将再次都指向X。
请注意，如果前一步是对它们两个来说都在循环中，它们都指向X-1。如果前一步只在slow的循环中，则它们指向不同的元素。
X-2，X-3等同理。
因此，在前进过程中，它们第一次指向相同的元素是从循环外部到达的循环的第一个元素，这就是你要找的重复元素。

- Dave

1

让我补充一下，这仅是对 @Khatri 算法的解释，他的回答很好，你应该接受他的答案而不是我的。 - Dave

1

更快/更慢的指针在循环中的某个位置第一次相遇，但不一定是在第一个（因此重复的）元素。这就是为什么需要第二步，其中您快速返回开始并将其和慢速移动（每次1个）。此时，我们知道一旦快速进入循环，它将指向与慢速相同的元素，因此我们可以使用此来识别第一个元素，我们知道它必须是重复的元素。 - Dave

嗨，戴夫，再次阅读你的评论，“slow将总共移动2k步，而fast将从起点移动k步，所以它们将再次指向X”，我认为这是错误的，因为这一次，slow/fast并没有从同一个点（即起点）开始。如果我错了，请随意纠正我。谢谢。 - Lin Ma

1

如果k是快指针和慢指针第一次相遇的位置，那么在k步之后，快指针移动了2k步，而慢指针只移动了k步。现在我们将快指针移回到0，并开始每次移动1步而不是2步。从0开始，在k个1步移动中，它位于位置k。慢指针最初位于位置k，因此在另外k个1步移动中，它位于位置2k。我们已经知道位置2k与位置k相同。 - Dave

1

@LinMa 假设我们开始快速移动两次每秒，慢速移动一次每秒，它们在循环中的某个位置x相遇，用k秒表示。然后我们将快速重置为零，并更改其速度为每秒移动一次。现在快速和慢速以相同的速度移动。另外k秒后，它们都回到了x。值得注意的是，如果我们将时钟倒退一秒，则它们都以相同的速度向后移动，因此只要快速仍在循环中，它将等于慢速。 - Dave

显示剩余7条评论

1

由于您不能使用任何额外的空间，因此使用另一个哈希表将被排除。

现在，针对现有数组进行哈希的方法可以实现，如果我们被允许就地修改数组。

算法：

1）从第一个元素开始。

2）对第一个元素进行哈希，并对哈希值应用转换。假设这个转换是使值为负数。

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

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

这种转换是必需的，因为如果我们要使用哈希方法，那么对于哈希相同键值的情况，就必须发生碰撞。

我无法想象在不使用额外空间和不修改数组的情况下如何使用哈希。

- basav

2

您不能修改现有的数组。 - n. m.

1

"我想不到一种在没有额外空间且不修改数组的情况下可以使用哈希的方式。"……同意。如果要使用哈希，则必须修改数组，否则不可能。 - basav

@basav，你的想法很聪明，我同意n.m.的观点，我们不应该修改数组。感谢分享。 - Lin Ma

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Khatri · Accepted Answer

以下是使用弗洛伊德循环检测算法的代码：

请注意以下内容：

#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]。