数据结构
网络
关系数据库管理系统 (RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
时尚研究
法律研究使用C++查找范围内缺失的一个数字
在这个问题中，我们得到一个大小为n的数组arr[]。我们的任务是查找范围内缺失的一个数字。
该数组包含从最小值到（最小值 + n）的所有值。范围内的一个元素缺失于数组中。我们需要找到这个缺失的值。
让我们来看一个例子来理解这个问题：
输入
arr[] = {4, 8, 5, 7}输出
6
解决方案方法
解决这个问题的一个简单方法是通过排序数组并找到从最小值开始的范围内第一个不在数组中但存在于范围内的元素来搜索缺失的元素。
这种解决方案是一种简单的方法，它将在O(n log n)的时间复杂度内解决问题。
另一种以更短时间解决问题的方法是使用数组的值和范围的XOR。我们将找到范围内所有值的XOR，以及数组中所有值的XOR。这两个值的XOR将是我们的缺失值。
示例
程序说明了我们解决方案的工作原理
#include <bits/stdc++.h>
using namespace std;
int findMissingNumArr(int arr[], int n){
int arrMin = *min_element(arr, arr+n);
int numXor = 0;
int rangeXor = arrMin;
for (int i = 0; i < n; i++) {
numXor ^= arr[i];
arrMin++;
rangeXor ^= arrMin;
}
return numXor ^ rangeXor;
}
int main(){
int arr[] = { 5, 7, 4, 8, 9};
int n = sizeof(arr)/sizeof(arr[0]);
cout<<"The missing value in the array is "<<findMissingNumArr(arr, n);
return 0;
}输出
The missing value in the array is 6
更新于：2022年2月11日
427 次浏览
广告