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.```
输出
First Missing element is : 6
时间复杂度: O(Logn)
辅助空间 : O(logn),其中logn是递归堆栈树的大小。