資料結構
網路
關係資料庫管理系統 (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 次瀏覽
廣告