在排序列表中找到第一个"缺失"的数字

Question

假设我有连续的整数范围[0, 1, 2, 4, 6],其中第一个3是"缺失"数字.我需要一个算法来找到第一个"洞".由于范围非常大(可能包含2^32条目),因此效率很重要.数字范围存储在磁盘上; 空间效率也是一个主要问题.

什么是最好的时间和空间效率算法？

Answer 1

使用二进制搜索.如果一系列数字没有孔,那么范围的结束和开始之间的差异也将是该范围中的条目数.

因此,您可以从整个数字列表开始,并根据前半部分是否有间隙来切断前半部分或后半部分.最终你会来到一个有两个条目的范围,中间有一个洞.

时间的复杂性是O(log N).与线性扫描相比,最坏的情况是O(N).

Answer 2

由于从 0 到n - 1 的数字在数组中排序，因此第一个数字应与其索引相同。也就是说，数字 0 位于索引 0 的单元格，数字 1 位于索引 1 的单元格，依此类推。如果缺失的数字表示为m。小于m 的数字位于索引与值相同的单元格中。

数字m + 1 位于索引为m 的单元格，数字m + 2 位于索引为m + 1 的单元格，依此类推。我们可以看到，缺失的数字m是第一个与其值不相同的单元格。

因此，需要在数组中查找第一个与其值不相同的单元格。由于数组是排序的，我们可以基于二分搜索算法 在 O(lg n ) 时间内找到它，如下所示：

int getOnceNumber_sorted(int[] numbers)
{
    int length = numbers.length
    int left = 0;
    int right = length - 1;
    while(left <= right)
    {
        int middle = (right + left) >> 1;
        if(numbers[middle] != middle)
        {
            if(middle == 0 || numbers[middle - 1] == middle - 1)
                return middle;
            right = middle - 1;
        }
        else
            left = middle + 1;
    }


    return -1;
}

这个解决方案借自我的博客：http://codercareer.blogspot.com/2013/02/no-37-missing-number-in-array.html。

Answer 3

根据上面@phs建议的方法,这里有C代码:

#include <stdio.h>

int find_missing_number(int arr[], int len) {
    int first, middle, last;
    first = 0;
    last = len - 1;
    middle = (first + last)/2;

    while (first < last) {
        if ((arr[middle] - arr[first]) != (middle - first)) {
            /* there is a hole in the first half */
            if ((middle - first) == 1 && (arr[middle] - arr[first] > 1)) {
                return (arr[middle] - 1);
            }

            last = middle;
        } else if ((arr[last] - arr[middle]) != (last - middle)) {
            /* there is a hole in the second half */
            if ((last - middle) == 1 && (arr[last] - arr[middle] > 1)) {
                return (arr[middle] + 1);
            }

            first = middle;
        } else {
            /* there is no hole */
            return -1;
        }

        middle = (first + last)/2;
    }

    /* there is no hole */
    return -1;
}

int main() {
    int arr[] = {3, 5, 1};
    printf("%d", find_missing_number(arr, sizeof arr/(sizeof arr[0]))); /* prints 4 */
    return 0;
}