java查找包含重复项的最小缺失数

Question

这是一个面试问题，但我无法及时解决，因此将其发布在此处：

给定一个n个整数的排序数组，其中每个整数的范围为0到m-1和m > n。查找数组中缺少的最小数字

例子 输入：{0, 1, 2, 6, 9}，n = 5，m = 10 产出：3

输入：{4, 5, 10, 11}，n = 4，m = 12 输出：0

其代码如下：

int findFirstMissing(int array[], int start, int end) {

    if(start  > end)
      return end + 1;

    if (start != array[start])
      return start;

    int mid = (start + end) / 2;

    if (array[mid] > mid)
      return findFirstMissing(array, start, mid);
    else
      return findFirstMissing(array, mid + 1, end);
}

现在的问题是，输入数组也可以有重复项：

input = [0, 1, 1, 2, 3, 3, 4, 5, 5, 7]

output = 6

我如何有效地解决它？可以应用什么样的优化

Answer 1

此解决方案在O(N)时间内工作，并使用O(1)额外内存：

public class Test {
    public static void main(String[] args) {
        int m = 5;
        int[] data = new int[] {0, 1, 1, 2, 3, 3, 4, 5};

        int current = 0;
        for (int i = 0; i < data.length; ++i) {
            if (current == data[i]) {
                current++;
            }
        }

        if (current >= m) {
            System.out.println("All is here");
        } else {
            System.out.println(current);
        }
    }
}

注意：n实际上被忽略，我使用了data.length

Answer 2

解决方案

    public static void main(String[] args) {
    Collection<Integer> input = new LinkedList<Integer>(Arrays.asList(10, 9, 7, 6, 5, 4, 3, 2, 1));
    NavigableSet<Integer> sortedOriginal = new TreeSet<Integer>(input);

    NavigableSet<Integer> numbers = new TreeSet<Integer>();
    for(int i=sortedOriginal.first();i<=sortedOriginal.last();i++){
        numbers.add(i);
    }

    for(Integer x : numbers){
        if(!sortedOriginal.contains(x)){
            System.out.println(x);
            break;
        }
    }
}

Answer 3

可以很容易地证明，您必须在O（n）时间内完成此操作，因为如果不检查每个值，您无法区分两个表：

1,2,_3_,4,5,7

及

1,2,_2_,4,5,7