用 C++ 编写一个程序,在给定的未排序整数数组中找到缺失的正数
假设我们给出了一个未排序的整数数组。任务是在[0到n]范围内找到给定数组中不存在的正缺失数。例如,
输入1-
N = 9 arr = [0,2,5,9,1,7,4,3,6]
输出-
8
说明-在给定的未排序数组中,'8'是唯一缺少的正整数,因此输出为'8'。
输入2 -
>N= 1 arr= [0]
输出-
1
说明-在给定的数组中,“1”是唯一缺少的正整数,因此输出为“1”。
解决这个问题的方法
有几种方法可以解决这个特定问题。然而,我们可以在线性时间O(n)和常数空间O(1)中解决这个问题。
因为我们知道我们的数组大小为n,并且它包含的元素正好在[0到n]范围内。因此,如果我们对每个元素及其索引与“n”进行XOR运算,那么我们可以找到作为数组中缺少的唯一数字的结果数字。
输入N大小的数组,元素在[0到n]范围内。
整数函数findMissingNumber(intarr[],intsize)将数组及其大小作为输入并返回缺失的数字。
让我们将n作为缺失的数字来执行XOR运算。
迭代所有数组元素,并对每个数组元素及其索引执行XOR操作,以丢失数字,即n。
现在返回丢失的数字。
示例
#includeusing namespace std; int findMissingNumber(int *arr, int size){ int missing_no= size; for(int i=0;i 输出结果 如果我们运行上面的代码,那么它会打印输出,
5如果我们对数组的每个元素及其索引执行XOR操作,它将打印数组中缺少的“5”。