ค้นหาองค์ประกอบที่ขาดหายไปของช่วงใน C++

ในปัญหานี้ เราได้รับอาร์เรย์ arr[] ขนาด n และจุดเริ่มต้นและ endelement แสดงถึงช่วง งานของเราคือค้นหาองค์ประกอบที่ขาดหายไปของช่วง

คำอธิบายปัญหา − เราจะหาองค์ประกอบของช่วงที่ไม่มีอยู่ในช่วง

มาดูตัวอย่างเพื่อทำความเข้าใจปัญหากัน

อินพุต

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 else mark arr[i] =false ในตอนท้าย เราจะสำรวจ booleanArray และพิมพ์องค์ประกอบทั้งหมดที่ทำเครื่องหมายว่าเป็นเท็จ

โปรแกรมเพื่อแสดงการทำงานของโซลูชันของเรา

ตัวอย่าง

#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