编写一个 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(int arr[], int size) 以数组及其大小作为输入，并返回缺失的数字。

  • 让我们将n 作为缺失的数字来执行 XOR 运算。

  • 遍历所有数组元素，并对每个数组元素及其索引与缺失数字n执行 XOR 运算。

  • 现在返回缺失的数字。

示例

实时演示

#include<bits/stdc++.h>
using namespace std;
int findMissingNumber(int *arr, int size){
   int missing_no= size;
   for(int i=0;i<size;i++){
      missing_no^= i^arr[i];
   }
   return missing_no;
}
int main(){
   int n= 6;
   int arr[n]= {0,4,2,1,6,3};
   cout<<findMissingNumber(arr,n)<<endl;
   return 0;
}

输出

如果我们运行以上代码，它将打印输出为：

5

如果我们对数组的每个元素及其索引执行 XOR 运算，它将打印“5”，它在数组中缺失。

更新于: 2021 年 2 月 5 日

395 次查看

开启你的 职业生涯

通过完成课程获得认证

开始学习
广告