在这个问题中,我们得到了一个大小为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
您可以通过多种方式解决此问题。他们是,
一种简单的解决方法是直接检查数组中范围的所有元素。为此,我们将对数组进行排序,然后在数组中找到范围的第一个元素,然后查找并打印缺少的元素。
该程序说明了我们解决方案的工作原理,
#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<<"缺少的元素是 "; findMissingElements(arr, n, low, high); return 0; }输出结果
缺少的元素是 5 8 9
解决该问题的另一种方法是使用数组。我们将创建一个大小为布尔值的数组(结束-开始)。对于此数组的每个元素,我们将发现数组中是否存在(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<<"缺少的元素是 "; findMissingElements(arr, n, low, high); return 0; }输出结果
缺少的元素是 5 8 9
解决该问题的另一种方法是使用哈希表。将数组的所有元素插入哈希表,并在插入后遍历范围并打印范围中不存在的所有元素。
该程序说明了我们解决方案的工作原理,
#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<<"缺少的元素是 "; findMissingElements(arr, n, low, high); return 0; }输出结果
缺少的元素是 5 8 9