Tìm các phần tử bị thiếu của một dải ô trong C ++

Trong bài toán này, chúng ta được cung cấp một mảng arr [] có kích thước n và phần bắt đầu và phần cuối biểu thị phạm vi. Nhiệm vụ của chúng ta là Tìm các phần tử còn thiếu của một dải ô.

Mô tả sự cố - chúng tôi sẽ tìm các phần tử của phạm vi không có trong phạm vi.

Hãy lấy một ví dụ để hiểu vấn đề,

Đầu vào

arr[] = {4, 6, 3, 7}, start = 3, end = 8

Đầu ra

5, 8

Giải thích

Phạm vi là [3, 4, 5, 6, 7, 8]

Mảng là {4, 6, 3, 7}

Các phần tử của dải ô không có trong mảng là 5, 8

Phương pháp tiếp cận giải pháp

Bạn có thể giải quyết vấn đề này bằng nhiều cách. Họ là,

#Approach 1

Một cách tiếp cận giải pháp đơn giản là kiểm tra trực tiếp tất cả các phần tử của phạm vi trong mảng. Đối với điều này, chúng tôi sẽ sắp xếp mảng và sau đó tìm phần tử đầu tiên của phạm vi trong mảng, sau đó tìm và in các phần tử bị thiếu.

Chương trình minh họa hoạt động của giải pháp của chúng tôi,

Ví dụ

#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;
}

Đầu ra

The missing elements are 5 8 9

#Approach 2

Một cách tiếp cận khác để giải quyết vấn đề là sử dụng một mảng. Chúng ta sẽ tạo một mảng boolean có kích thước (end - start). Đối với mỗi phần tử của mảng này, chúng ta sẽ tìm xem (i + start) có trong mảng hay không. Nếu nó hiện diện, đánh dấu arr [i] =true else mark arr [i] =false. Cuối cùng, chúng tôi sẽ duyệt qua booleanArray và in tất cả các phần tử được đánh dấu là false.

Chương trình minh họa hoạt động của giải pháp của chúng tôi,

Ví dụ

#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;
}

Đầu ra

The missing elements are 5 8 9

#Approach 3

Một cách tiếp cận khác để giải quyết vấn đề là sử dụng bảng băm. Chèn tất cả các phần tử của mảng vào bảng băm và sau khi chèn qua dải ô và in tất cả các phần tử không có trong dải.

Chương trình minh họa hoạt động của giải pháp của chúng tôi,

Ví dụ

#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;
}

Đầu ra

The missing elements are 5 8 9