好资源导航 » 文章资讯 » 用 C++ 编写一个程序，在给定的未排序整数数组中找到缺失的正数

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

2023-06-21 10:15:02 95

假设我们给出了一个未排序的整数数组。任务是在[0到n]范围内找到给定数组中不存在的正缺失数。例如，

输入1-

N = 9 arr = [0,2,5,9,1,7,4,3,6]

输出-

说明-在给定的未排序数组中，'8'是唯一缺少的正整数，因此输出为'8'。

输入2 -

>N= 1 arr= [0]

输出-

说明-在给定的数组中，“1”是唯一缺少的正整数，因此输出为“1”。

解决这个问题的方法

有几种方法可以解决这个特定问题。然而，我们可以在线性时间O(n)和常数空间O(1)中解决这个问题。

因为我们知道我们的数组大小为n，并且它包含的元素正好在[0到n]范围内。因此，如果我们对每个元素及其索引与“n”进行XOR运算，那么我们可以找到作为数组中缺少的唯一数字的结果数字。

输入N大小的数组，元素在[0到n]范围内。

整数函数findMissingNumber(intarr[],intsize)将数组及其大小作为输入并返回缺失的数字。

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

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

现在返回丢失的数字。

示例

#include
using namespace std;
int findMissingNumber(int *arr, int size){
   int missing_no= size;
   for(int i=0;i输出结果
如果我们运行上面的代码，那么它会打印输出，
5
如果我们对数组的每个元素及其索引执行XOR操作，它将打印数组中缺少的“5”。

返回顶部
514930285
czq8825@qq.com

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

解决这个问题的方法

示例

热门推荐

随机推荐