在一个列表中找到可能重复的整数之一。

Question

给定一个包含 n+1 个整数的数组，每个整数的范围是 1 到 n，找到一个重复出现的整数。

我在面试中被问到这个问题。这是我的回答：鸽巢原理表明一定会有重复。我尝试使用二分查找的方法，在 Matlab 中编写了以下代码：

top = 0;
bot = 0;
for i=1:n+1
  if P[i] > n/2 
    top = top+1;
  else
    bot = bot+1;
end

因此，我认为其中一个top或bot必须再次通过PhP大于n / 2。取该范围并重复。

我认为这是一个相当不错的解决方案，但面试官暗示可以做得更好。如果您知道任何更好的解决方案，请发布。

- Daniel

---

但是可能会有很多重复，所以我认为那些问题和我的不一样。而且排序非常慢。比我的答案慢得多。 - Daniel

@Matt Ball和其他收件人，我认为我们行动过快了。这两个重复项并不真的相同。 - PengOne

我同意，这不是同一个问题。值得重新开放。 - Nemo

@Daniel：你所说的“大量重复”是指一个整数重复多次还是多个整数重复（可能超过一次）？ - user616736

可以在1和n之间任意选择数字，且可以重复使用，因此这个问题非常困难。 - Daniel

Answer 1

我不确定你是如何定义“更好”的，但也许这个可以符合条件。至少它与你的解决方案和链表问题的解决方案不同（开个玩笑）。

如果我们创建了一个路径

n+1 --> array[n+1] --> array[array[n+1]] --> ...

如果且仅当array^k[n+1] = array^l[n+1]对于一些k != l, 即存在重复时，则此路径包含循环。现在问题变成了一个常见的链表问题，可以按如下方式解决。

在第一个节点上启动两个粒子。让第一个粒子以单位速度移动，第二个粒子以两倍的单位速度移动。然后，如果存在循环，第二个粒子将最终回到第一个粒子的后面，并且它们最终将相同。为什么？好吧，如果你将粒子想象成在圆上（一旦找到循环就会这样），那么每个时间单位第二个粒子就会向第一个粒子的方向靠近一步。因此它们必须最终相撞。一旦他们相撞，你就找到了一个循环。要找到重复的值，只需通过让其中一个粒子保持静止而让另一个粒子再次运行循环来获取循环的长度。然后重新从开始位置启动两个粒子，让一个粒子向前移动循环长度，然后使两个粒子之间保持恒定距离同时运行，直到它们再次在循环的开始处相遇。

有些评论者对我没有包括如何在链表中找到循环的所有细节感到愤怒，现在这里它就是。不能保证这不会有错误（毕竟这是类似Matlab的伪代码），但它至少应该解释了这个想法。

%% STEP 1: find a point in the cycle of the linked list using a slow and fast particle
slow = n+1;
fast = n+1;
for i=1 to n+1
    slow = array[slow];
    fast = array[array[fast]];
    if (slow == fast)
        break;
end

%% STEP 2: find the length of the cycle by holding one particle fixed
length = 1;
fast = array[fast]
while fast != slow
    fast = array[fast];
    length = length+1;
end

%% STEP 3: find the repeated element by maintaining constant distance between particles
slow = n+1;
fast = n+1;
for i=1 to length
    fast = array[fast];
end
while fast != slow
    fast = array[fast];
    slow = array[slow];
end

%% STEP 4: return the repeated entry
return slow;

我从n+1开始，因为array[i]在1和n之间，所以没有一个粒子会被送回到n+1。这使得对数组进行最多一次（无序的）遍历，并跟踪两个粒子（慢速和快速）和一个整数（长度）。因此，空间复杂度为O(1)，时间复杂度为O(n)。

- PengOne

---

@Daniel：不行。这是检测列表中循环的标准“指针追踪”技术。慢指针每步移动+1，快指针每步移动+2，因此快指针每步都会比慢指针多+1。它不能跳过它。 - Nemo

@Daniel：是个好问题，但想一想当快粒子从慢粒子后面追上来时会发生什么。如果快粒子落后一步，则它们在下一步碰撞。如果快粒子落后两步，则它们将在两步内碰撞。明白了吗？ - PengOne

这是线性时间和常数空间，可以证明是最优的。你至少需要线性时间（必须查看每个数组条目），并且你至少需要常数空间。 - ShreevatsaR

解决方案从来没有是不正确的，只是不完整。它阐明了核心思想（循环检测），对于任何足够用心思考并完成算法的人来说已经足够了。但是，完整的答案更好，现在已经是完整的了。也许要感谢你的评论。 :-) - ShreevatsaR

啊，关键部分从第n+1个元素开始，因为它不能成为任何“普通”的无重复循环的一部分...非常聪明！ - j_random_hacker

Answer 2

如果您知道有一个数字是重复的，您可以通过将它们全部相加并从1到n的数字总和中减去数字总和来找到它：

duplicate = sum P[i] - n(n+1)/2

如果没有，您可以遍历数组并将每个数字放入哈希表中。如果数字已经存在，则为重复项。这也是O（n），假设哈希表操作为O（1）。

或者更好的方法-为了避免使用哈希表，您可以使用大小为n的布尔数组：

int[] P = new int[] { 3, 2, 5, 1, 4, 2 };
bool[] Q = new bool[6];

foreach( var p in P ){
    if ( Q[p] ) {
        Console.WriteLine("Duplicate: " + p);
        break;
    }
    Q[p] = true;
}

- Petar Ivanov

---

这个第二种解决方案比二进制的慢一些，我认为。 - Daniel

不完全是这样。这种方法只需要一次遍历数组，而二进制解决方案需要多次遍历数组的某些部分。 - Petar Ivanov

没错。但当你说“慢”的时候，指的是时间。所以它并不是慢！它更快，只是占用更多的空间。 - Petar Ivanov

这是线性时间和线性空间，时间上是最优的。它绝对比问题中所谓的二分查找解决方案更快。尽管空间可以像PengOne的答案那样改进，但时间上也是最优的。 - ShreevatsaR

这个占用更多的空间，但我认为它比我的答案更好。谢谢。 - Daniel

Answer 3

我们使用 圆检测 的思路来解决这个问题。

我们需要做的是首先找到圆的起点，然后在圆内找到重复的点。

以下是 c++ 代码：

int findDuplicate(vector<int>& nums) {
    int slow = nums[0];
    int fast = nums[nums[0]];

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

    return slow;
}

- Boooooooooms

Answer 4

这个方法的工作方式与@PengOne的答案类似，但我认为它更简单。

解释：

这种方法将数组视为一个图，其中索引i处的值指向索引a[i]-1（因此值1指向索引0）。至少有一个重复的数字，因此图形将是循环的。有n+1个元素，最大值为n，因此最后一个节点a[n+1]永远不会成为循环的一部分，但会进入循环。这很重要，因为这个最后的节点是遍历的起始节点。请注意，如果循环中的节点被用作慢速（1x）和快速（2x）指针的起始节点，则它们在同一节点相遇，这是没有用的。我们将汇合的节点称为相遇节点。如果相遇节点距离循环节点有k个跳跃，则起始节点也将距离循环节点有k个跳跃。这个逻辑与在循环链接列表中找到循环节点相同。数组最多遍历3次，因此时间复杂度为O(n)，空间复杂度为O(1)。

算法：

1. 从最后一个节点（a[n+1]）开始，使用 slow（1x）和 fast（2x）指针找到 meet node。
2. 从 meet node 和 start node 分别向前移动两个指针（1x），它们将会汇合在 cycle node 上（重复的数字指向 cycle node）。

代码：

//pseudocode
//O(n) time, O(1) space
findrepeating(a):
    x = findrepeating(a, findmeet(a), a[a.length() -1])
    return x

findmeet(a):
    slow = fast = a[a.length() -1]
    while true:
        slow = a[slow-1]
        fast = a[a[fast-1]-1]
        if slow == fast:
            break
    meet = slow // or fast
    return meet

findrepeating(a, meet, start):
    m = meet
    s = start
    while m != s:
        m = a[m-1]
        s = a[s-1]
    return m // or s

- hIpPy

Answer 5

这里有一个简单的解决方案：

从数组开始创建一个二叉搜索树。每当您在插入BST时遇到重复元素，则将该元素存储在另一个重复元素数组中，并继续您的循环。我们甚至不需要对数组进行排序就可以找到重复项。

这只是我的想法。我在面试中被问到了同样的问题，这就是我的答案。

- Vijay

Answer 6

for(int i=n+1;i!=a[i];i=a[i]);

cout<<i;

- ans