C++程序查找最小缺失的数字

给定一个 排序的 包含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

输入： {0, 1, 2, 3}，n=4，m=5
输出： 4

输入： {0, 1, 2, 3, 4, 5, 6, 7, 10}，n=9，m=11
输出： 8

方法1（使用二分查找）

对于i = 0到m-1，在数组中进行二分查找。如果i不在数组中，则返回i。

时间复杂度：O(m log n)

方法2（线性查找）

如果arr[0]不为0，则返回0。否则，从索引0开始遍历输入数组，并针对每个元素a[i]和a[i+1]找到它们之间的差异。如果差异大于1，则a[i]+1是缺失的数字。

时间复杂度：O(n)

方法3（使用修改后的二分查找）

在标准二分查找过程中，被搜索的元素与中间元素进行比较，并根据比较结果决定搜索是否结束或前往左半部分或右半部分。

在此方法中，我们修改标准二分查找算法，将中间元素与其索引进行比较，并根据这个比较做出决策。

如果第一个元素与其索引不同，则返回第一个索引
否则获取中间索引mid
- 如果arr[mid]大于mid，则所需元素位于左半部分。
- 否则所需元素位于右半部分。

// C++ program to find the smallest elements
// missing in a sorted array.
#include<bits/stdc++.h>
using namespace std;
 
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;
 
    // 左半部分包含0到mid的所有元素
    if (array[mid] == mid)
        return findFirstMissing(array,
                            mid+1, end);
 
    return findFirstMissing(array, start, mid);
}
 
// Driver code
int main()
{
    int arr[] = {0, 1, 2, 3, 4, 5, 6, 7, 10};
    int n = sizeof(arr)/sizeof(arr[0]);
    cout << "Smallest missing element is " <<
        findFirstMissing(arr, 0, n-1) << endl;
}
 
// This code is contributed by
//Shivi_Aggarwal```

输出

Smallest missing element is 8

注意： 如果数组中有重复元素，则此方法无效。

时间复杂度： O(logn)

辅助空间： O(logn)

另一种方法： 思路是使用递归二分查找找到最小缺失的数字。以下是步骤的说明：

如果数组的第一个元素不为0，则最小缺失数字为0。
如果数组的最后一个元素是N-1，则最小缺失数字是N。
否则，从第一个和最后一个索引中找到中间元素，并检查中间元素是否等于期望元素，即first + middle_index。
- 如果中间元素是期望元素，则最小缺失元素在中间的右侧搜索空间中。
- 否则，最小缺失数字在中间的左侧搜索空间中。

下面是上述方法的实现：

//C++ program for the above approach
#include <bits/stdc++.h>
 
using namespace std;
 
// Program to find missing element
int findFirstMissing(vector<int> arr , int start ,
                        int  end,int first)
{
 
  if (start < end)
  {
    int mid = (start + end) / 2;
 
    /** Index matches with value
      at that index, means missing
      element cannot be upto that po*/
    if (arr[mid] != mid+first)
      return findFirstMissing(arr, start,
                                 mid , first);
    else
      return findFirstMissing(arr, mid + 1,
                                 end , first);
  }
  return start + first;
 
}
 
// Program to find Smallest
// Missing in Sorted Array
int findSmallestMissinginSortedArray(vector<int> arr)
{
   
  // Check if 0 is missing
  // in the array
  if(arr[0] != 0)
    return 0;
 
  // Check is all numbers 0 to n - 1
  // are present in array
  if(arr[arr.size() - 1] == arr.size() - 1)
    return arr.size();
 
  int first = arr[0];
 
  return findFirstMissing(arr, 0, arr.size() - 1, first);
}
 
 
// Driver program to test the above function
int main()
{
    vector<int> arr = {0, 1, 2, 3, 4, 5, 7};
    int n = arr.size();
 
    // Function Call
    cout<<"First Missing element is : "<<findSmallestMissinginSortedArray(arr);
}
 
// This code is contributed by mohit kumar 29.```