数据结构
网络
关系数据库管理系统 (RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化学
生物
数学
英语
经济学
心理学
社会学
时尚研究
法律研究在 C++ 中查找范围内的缺失元素
在这个问题中，我们给定一个大小为 n 的数组 arr[] 和表示范围的起始和结束元素。我们的任务是查找范围内的缺失元素。
问题描述 - 我们将查找范围内不在数组中的元素。
让我们来看一个例子来理解这个问题：
输入
arr[] = {4, 6, 3, 7}, start = 3, end = 8输出
5, 8
解释
范围是 [3, 4, 5, 6, 7, 8]
数组是 {4, 6, 3, 7}
数组中不存在的范围元素是 5, 8
解决方案方法
您可以通过多种方式解决此问题。它们是：
方法 1
一种简单的解决方案方法是直接在数组中检查范围的所有元素。为此，我们将对数组进行排序，然后在数组中查找范围的第一个元素，然后查找并打印缺失的元素。
程序说明了我们解决方案的工作原理：
示例
#include <bits/stdc++.h>
using namespace std;
void findMissingElements(int arr[], int n, int low, int high){
sort(arr, arr + n);
int* pointerVal = lower_bound(arr, arr + n, low);
int index = pointerVal - arr;
int i = index, x = low;
while (i < n && x <= high) {
if (arr[i] != x)
cout << x << " ";
else
i++;
x++;
}
while (x <= high)
cout<<x++<<" ";
}
int main(){
int arr[] = { 4, 6, 3, 7 };
int n = sizeof(arr) / sizeof(arr[0]);
int low = 3, high = 9;
cout<<"The missing elements are ";
findMissingElements(arr, n, low, high);
return 0;
}输出
The missing elements are 5 8 9
方法 2
解决这个问题的另一种方法是使用数组。我们将创建一个大小为 (end - start) 的布尔数组。对于此数组的每个元素，我们将查找 (i+start) 是否存在于数组中。如果存在，则将 arr[i] 标记为 true，否则将 arr[i] 标记为 false。最后，我们将遍历 booleanArray 并打印所有标记为 false 的元素。
程序说明了我们解决方案的工作原理：
示例
#include <bits/stdc++.h>
using namespace std;
void findMissingElements(int arr[], int n, int start, int end){
bool boolArray[end - start + 1] = { false };
for (int i = 0; i < n; i++) {
if (start <= arr[i] && arr[i] <= end)
boolArray[arr[i] - start] = true;
}
for (int i = 0; i <= end - start; i++) {
if (boolArray[i] == false)
cout<<(start + i)<<"\t";
}
}
int main(){
int arr[] = { 4, 6, 3, 7 };
int n = sizeof(arr) / sizeof(arr[0]);
int low = 3, high = 9;
cout<<"The missing elements are ";
findMissingElements(arr, n, low, high);
return 0;
}输出
The missing elements are 5 8 9
方法 3
解决这个问题的另一种方法是使用哈希表。将数组的所有元素插入哈希表，插入后遍历范围并打印范围内不存在的所有元素。
程序说明了我们解决方案的工作原理：
示例
#include <bits/stdc++.h>
using namespace std;
void findMissingElements(int arr[], int n, int start, int end){
unordered_set<int> arrEle;
for (int i = 0; i < n; i++)
arrEle.insert(arr[i]);
for (int i = start; i <= end; i++)
if (arrEle.find(i) == arrEle.end())
cout<<i<<"\t";
}
int main(){
int arr[] = { 4, 6, 3, 7 };
int n = sizeof(arr) / sizeof(arr[0]);
int low = 3, high = 9;
cout<<"The missing elements are ";
findMissingElements(arr, n, low, high);
return 0;
}输出
The missing elements are 5 8 9
更新于：2021年3月12日
372 次浏览
广告