ค้นหาองค์ประกอบที่หายไปจากอาร์เรย์ที่ซ้ำกันใน C++

แนวคิด

ในส่วนที่เกี่ยวกับอาร์เรย์สองชุดที่ให้มาซึ่งซ้ำกันยกเว้นหนึ่งองค์ประกอบ ซึ่งหมายความว่าองค์ประกอบหนึ่งจากอาร์เรย์หนึ่งหายไป หน้าที่ของเราคือกำหนดองค์ประกอบที่ขาดหายไปนั้น

อินพุต

arr1[] = {2, 5, 6, 8, 10}
arr2[] = {5, 6, 8, 10}

ผลลัพธ์

2

2 หายไปจากอาร์เรย์ที่สอง

อินพุต

arr1[] = {3, 4, 5, 6}
arr2[] = {3, 4, 5, 6, 7}

ผลลัพธ์

7

ไม่มี 7 จากอาร์เรย์แรก

วิธีการ

ในที่นี้ เราใช้วิธีแก้ปัญหาง่ายๆ วิธีหนึ่งที่เราทำซ้ำผ่านอาร์เรย์ และตรวจสอบองค์ประกอบตามองค์ประกอบ และทำเครื่องหมายองค์ประกอบที่ขาดหายไปเมื่อตรวจพบองค์ประกอบที่ไม่ตรงกัน แต่ข้อเสียของโซลูชันนี้คือต้องใช้เวลาเชิงเส้นมากกว่าขนาดของอาร์เรย์

เราสามารถใช้โซลูชันอื่นที่มีประสิทธิภาพซึ่งอิงตามแนวทางการค้นหาแบบไบนารี เราปฏิบัติตามอัลกอริทึมด้านล่างซึ่งมีการอธิบายทีละขั้นตอน -

• เริ่มการค้นหาไบนารีในอาร์เรย์ที่ใหญ่กว่าและรับค่ากลางเป็น (ต่ำ + สูง) / 2
• พบว่าหากค่าจากทั้งสองอาร์เรย์เท่ากัน องค์ประกอบที่ขาดหายไปจะต้องอยู่ทางด้านขวา ดังนั้นให้ทำเครื่องหมายที่ระดับต่ำเป็นระดับกลาง
• มิฉะนั้นให้ทำเครื่องหมายสูงเป็นระดับกลางเนื่องจากองค์ประกอบที่ขาดหายไปจะต้องอยู่ในด้านซ้ายของอาร์เรย์ที่ใหญ่กว่าหากองค์ประกอบกลางไม่เหมือนกัน
• เราต้องจัดการกรณีพิเศษแยกกัน เพราะสำหรับองค์ประกอบเดี่ยวและอาร์เรย์องค์ประกอบศูนย์ องค์ประกอบเดี่ยวจะเป็นองค์ประกอบที่ขาดหายไป

มีข้อสังเกตว่าถ้าองค์ประกอบแรกเองไม่เท่ากันองค์ประกอบนั้นจะเป็นองค์ประกอบที่ขาดหายไป

ตัวอย่าง

// C++ program to find missing element from same
// arrays (except one missing element)
#include <bits/stdc++.h>
using namespace std;
// Shows function to determine missing element based on binary
// search approach. arrA[] is of larger size and
// Q is size of it. arrA[] and arrB[] are assumed
// to be in same order.
int findMissingUtil(int arrA[], int arrB[], int Q){
   // Considers special case, for only element which is
   // missing in second array
   if (Q == 1)
      return arrA[0];
   // Considers special case, for first element missing
   if (arrA[0] != arrB[0])
      return arrA[0];
   // Used to initialize current corner points
   int low = 0, high = Q - 1;
   // Iterate until low < high
   while (low < high){
      int mid = (low + high) / 2;
      // It has been observed that if element at mid indices are equal
      // then go to right subarray
      if (arrA[mid] == arrB[mid])
         low = mid;
      else
         high = mid;
         // So if low, high becomes contiguous, break
      if (low == high - 1)
      break;
   }
   // Now missing element will be at high index of
   // bigger array
   return arrA[high];
}
// So this function mainly does basic error checking
// and calls findMissingUtil
void findMissing(int arrA[], int arrB[], int P, int Q){
   if (Q == P-1)
      cout << "Missing Element is "
      << findMissingUtil(arrA, arrB, P) << endl;
   else if (P == Q-1)
      cout << "Missing Element is "
      << findMissingUtil(arrB, arrA, Q) << endl;
   else
   cout << "Invalid Input";
}
// Driver Code
int main(){
   int arrA[] = {2, 5, 6, 8, 10};
   int arrB[] = {5, 6, 8, 10};
   int P = sizeof(arrA) / sizeof(int);
   int Q = sizeof(arrB) / sizeof(int);
   findMissing(arrA, arrB, P, Q);
   return 0;
}

ผลลัพธ์

Missing Element is 2