用 C++ 编写一个程序，在给定的未排序整数数组中找到缺失的正数

  • Z时代
  • 2024-01-10
  • 分类：综合

假设我们给出了一个未排序的整数数组。任务是在 [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 运算。

  • 迭代所有数组元素，并对每个数组元素及其索引执行 XOR 操作，以丢失数字，即n。

  • 现在返回丢失的数字。

示例

#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”。

以上是 用 C++ 编写一个程序，在给定的未排序整数数组中找到缺失的正数 的全部内容， 来源链接： utcz.com/z/343876.html

回到顶部