c - 查找不在数组中的最小整数

Question

给定一个未排序的集合A，什么是找到最小整数的最有效解决方案，x它不是需要大于某个整数A的元素？xm

例如

输入：A = {7, 3, 4, 1},m = 5

输出：x = 6

我正在寻找 C 中的解决方案，但任何类型的伪代码都会有所帮助......这个问题可以在 O(n) 中解决，其中 n 是设置大小吗？

Answer 1

我使用额外的数组解决了它。这里的“len”是数组的长度。

int findMin(int *arr,int n,int len)
{
    int *hash;
            if(len==0)
               {return -1;  //fail 
                }
    hash=(int*)calloc(len,sizeof(int)); //hash function I'm using is f(x)=f(x)-n;
    int i;
    for(i=0;i<len;i++){
        if(arr[i]>n && arr[i]<len+n){  //because max element can't be more than n
            hash[arr[i]-n]++;
        }
    }

    i=1;
    while(i<len){
        if(hash[i]==0)
            return len+i;
        i++;
    }
            return len+n+1;
}

这个灵魂的顺序是 O(n) 运行时间和 O(n) 空间。

Answer 2

以下 Java 代码应该适合您：

public static int findMinNotInArray(int array[], int n) {
    int frequency[] = new int[array.length];

    if (n < max(array)) {
        for (int i = 0; i < array.length; i++) {
            if (array[i] > n && array[i] < n + array.length)
                frequency[array[i] - (n + 1)]++;
        }

        for (int i = 0; i < frequency.length; i++) {
            if (frequency[i] == 0)
                return i + n + 1;
        }
        return -1;
    } else {
        return n + 1;
    }
}

public static int max(int array[]) {
    int max = array[0];
    for (int i = 1; i < array.length; i++) {
        if (array[i] > max) {
            max = array[i];
        }
    }
    return max;
}

上面的代码只是简单地跟踪从n+1到的数字(n+1) + lengthOfA，这个范围内的任何一个是否存在于数组中！并返回第一个不存在的数字！

Answer 3

我认为，最可行的方法是先对数组进行排序。然后你可以对它进行二分搜索m，然后线性搜索下一个相邻点相距不止一个的点。

这种方法的复杂性是排序算法的复杂性，也就是说在大多数情况下是 O(nlogn)。