在小于线性的时间内,在排序的数组中找到副本

Question

今天,一位采访者问我这个问题.我的直接反应是我们可以简单地进行线性搜索,将当前元素与数组中的前一个元素进行比较.然后他问我如何在不到线性的时间内解决问题.

假设

• 数组已排序
• 只有一个副本
• 该数组仅填充数字[0, n],其中n是数组的长度.

示例数组:[0,1,2,3,4,5,6,7,8,8,9]

我试图想出一个分而治之的算法来解决这个问题,但我并不相信这是正确的答案.有没有人有任何想法？

Answer 1

可以使用修改的二进制搜索在O(log N)中完成:

从数组的中间开始:如果array [idx] <idx,则副本位于左侧,否则位于右侧.冲洗并重复.

Answer 2

如果数组中没有数字丢失,如示例所示,它可以在O(log n)中使用二进制搜索.如果a[i] < i,副本在之前i,否则它在之后i.

如果有一个号码缺席且一个号码重复,我们仍然知道如果a[i] < i副本必须在之前i和之前,则a[i] > i缺席号码必须在之前i和之后重复.但是,如果a[i] == i,我们不知道丢失的数字和重复是否都在之前i或之后i.在这种情况下,我没有看到子线性算法的方法.

Answer 3

我试图想出一个分而治之的算法来解决这个问题,但我并不相信这是正确的答案.

当然,你可以做二分搜索.

如果arr[i/2] >= i/2那么副本位于数组的上半部分,否则它位于下半部分.

while (lower != upper)
    mid = (lower + upper) / 2
    if (arr[mid] >= mid)
        lower = mid
    else
        upper = mid-1

由于每次迭代之间lower和之间的数组upper减半,因此算法在O(log n)中运行.

Java中的ideone.com演示