이 문제에서는 크기가 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
문제를 해결하는 또 다른 방법은 배열을 사용하는 것입니다. 우리는 크기의 부울 배열(끝 - 시작)을 생성할 것입니다. 이 배열의 각 요소에 대해 배열에 (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