是否有 O(n) 算法来查找数组中第一个缺失的数字？

Question

给定一个 n 整数数组，不一定排序，是否有 O(n) 算法来找到最小整数大于数组中的最小整数但不在数组中？

Answer 1

你可以使用按位XOR的技巧。

此方法具有 O(n) 的时间复杂度，它也适用于未排序的数组。

此外，请记住，这仅在数组中缺少一个元素时有效。

#include <stdio.h>

int main()
{
    int arr[] = { 1, 2, 4, 5, 6, 7 };
    int arr_size = sizeof(arr) / sizeof(arr[0]);
 
    int x = arr[0]; //XOR together all of the array elements
    for (int i = 1; i < arr_size; i++) 
    {
        x ^= arr[i];
    }
 
    int y = 1; //XOR together the numbers from 1 to size of array + 1
    for (int i = 2; i <= arr_size + 1; i++)
    {
        y ^= i;
    }
    
    int missing = x ^ y; //The missing number is going to be the XOR of the previous two.

    printf("%d", missing);

    return 0;
}

Answer 2

Given an array of n integers, without negative numbers, not necessarily sorted, is there an O(n) algorithm to find the least integer that is greater than the minimum integer in the array but that is not in the array?

这可以用 O(N) 时间复杂度来解决，其中 N 是数组中元素的数量。让我们称该数组为a1，算法如下：

求a1中的最小值（即 min）；
创建一个新数组 a2，大小等于 N；
用一个值来初始化数组 a2 以表示缺少元素，例如 min - 1；
遍历数组a1，对于每个位置，取该位置的元素e1 = a1[i]，且仅当e1不大于min - N标记a2访问上对应的位置，例如使用元素本身，即a2[e1 - min] = e1；如果 e1 大于 min - size 那么它显然不属于序列，可以忽略，因为在最坏的情况下第一个缺失值将是值 min + N + 1.
最后遍历数组a2，得到第一个元素=-1；这将是您第一个缺少的元素。

第 1、3、4 和 5 步，所有这些都考虑了最坏的情况 N。因此，该算法需要4N，即O(N)时间复杂度；

代码将直接实现；例如如下（对于数组 {5, 3, 0, 1, 2, 6}）：

#include <stdio.h>
#include <stdio.h>
#include <stdlib.h>

int find_min(int *array, int size){
    int min = array[0];
    for(int i = 0; i < size; i++)
        min = (array[i] < min) ? array[i] : min;
    return min;
}

void fill_array(int *array, int size, int missing_value){
     for(int i = 0; i < size; i++)
        array[i] = missing_value;
}

void mark_existing_values(int *s, int size, int *d, int min){
    for(int i = 0; i < size; i++){
        int elem = s[i];
        if(elem - min < size)
           d[elem - min] = elem;
    }
}

int find_first_missing_value(int *array, int size, int min){
     int missing_value = min - 1;
     for(int i = 0; i < size; i++){
         if(array[i] == missing_value){
            return i + min;
         }
     }
    return missing_value;
}


int main(){
    int array_size =  6;
    int array_example [] = {5, 3, 0, 1, 2, 6};
    int min = find_min(array_example, array_size);
    int *missing_values = malloc(array_size * sizeof(int));
    fill_array(missing_values, array_size, min - 1);
    mark_existing_values(array_example, array_size, missing_values, min);
    int value = find_first_missing_value(missing_values, array_size, min);
    printf("First missing value {%d}\n", value);
    free(missing_values);
    return 0;
}

输出：

第一个缺失值{4}

该算法也适用于负数，例如如果 int array_example [] = {-1, -3, 0, 3, 5, 6, 7, 8, 10};，则输出为：

First missing value {-2}

代码可以简化，如果在step 3和step 4中分别代替min - 1和a2[e1 - min] = e1，我们使用两个标志来表示丢失（例如， 0) 和现有值（例如， 1）。就像@Damien 代码中的展示一样。缺点是我们使用两个标志而不是一个。好处是它简化了代码，如果数组中的最小值是可以用 C 表示的最小值，我们将不会用 min - 1.

下溢

Answer 3

以下算法的复杂度为 O(n)。

这里假设缺失的元素一定是在最小值之后选择的
如果最小可能值是固定的，例如等于 0，则可以轻松修改算法。

一旦我们确定了最小值 a（在 O(n) 或 O(1) 中，如果该值事先已知），那么我们知道缺失值小于等于a + n，如果n是数组大小。

然后我们只需使用大小为n+1、present[n+1]的数组，初始化为0，然后查看所有值 arr[i]:

if (arr[i] <= a+n) present[arr[i] - a] = 1;

最后，在第三步中，我们只需检查数组 present[.]，并搜索第一个索引 k，这样 present[k]==0.

第一个缺失的数字等于a + k。

#include <stdio.h>
#include <stdlib.h>

int find_missing (int *arr, int n) {
    int vmin = arr[0];
    int *present = calloc (n+1, sizeof(int));
    for (int i = 1; i < n; ++i) {
        if (arr[i] < vmin) {
            vmin = arr[i];
        }
    }
    int vmax = vmin + n;
    for (int i = 0; i < n; ++i) {
        if (arr[i] <= vmax) {
            present[arr[i] - vmin] = 1;
        }
    }
    int k = 0;
    for (k = 0; k <= n; ++k) {
        if (present[k] == 0) break;
    }
    free(present);
    return vmin + k;
}


int main() {
    int arr[] = {2, 3, 5, 6, 8};
    int n = sizeof(arr)/sizeof(arr[0]);
    
    int missing = find_missing (arr, n);
    printf ("First missing element = %d\n", missing);
    return 0;
}

是否有 O(n) 算法来查找数组中第一个缺失的数字？

Is there an O(n) algorithm to find the first missing number in an array?

c

arrays

performance

big-o

time-complexity