ค้นหาองค์ประกอบที่ขาดหายไปในอาร์เรย์ที่เรียงลำดับของตัวเลขต่อเนื่องกันใน C++

แนวคิด

ในส่วนที่เกี่ยวกับอาร์เรย์อาร์เรย์ที่กำหนด[]ของจำนวนเต็ม n จำนวนเต็มที่แตกต่างกัน องค์ประกอบจะถูกจัดเรียงตามลำดับจากน้อยไปมากโดยมีองค์ประกอบที่ขาดหายไปหนึ่งรายการ งานของเราคือการกำหนดองค์ประกอบที่ขาดหายไป

อินพุต

array[] = {1, 2, 3, 4, 5, 6, 7, 9}

ผลลัพธ์

8

อินพุต

array[] = {-4, -2, -1, 0, 1, 2}

ผลลัพธ์

-3

อินพุต

array[] = {1, 2, 3, 4}

ผลลัพธ์

-1

ไม่มีองค์ประกอบใดขาดหายไป

วิธีการ

หลักการ

• มองหาความไม่สอดคล้องกัน:ตามหลักการนี้ ข้อแตกต่างระหว่างองค์ประกอบใดๆ และดัชนีจะต้องเป็น array[0] สำหรับทุกองค์ประกอบ

ตัวอย่าง

A[] ={1, 2, 3, 4, 5} -> สม่ำเสมอ

B[] ={201, 202, 203, 204} -> สม่ำเสมอ

C[] ={1, 2, 3, 5, 6} -> ไม่สอดคล้องกับ C[3] – 3 !=C[0] เช่น 5 – 3 !=1

• การระบุความไม่สอดคล้องกันช่วยในการสแกนอาร์เรย์เพียงครึ่งเดียวในแต่ละครั้งใน O(logN)

อัลกอริทึม

• กำหนดองค์ประกอบตรงกลางและตรวจสอบว่าสอดคล้องกันหรือไม่

• หากองค์ประกอบกลางมีความสอดคล้องกัน ให้ตรวจสอบว่าความแตกต่างระหว่างองค์ประกอบกลางและองค์ประกอบถัดไปมีค่ามากกว่า 1 หรือไม่ เช่น ตรวจสอบว่า array[mid + 1] – array[mid]> 1

  • ถ้าใช่ ดังนั้น array[mid] + 1 คือองค์ประกอบที่ขาดหายไป

  • ไม่เช่นนั้น เราต้องสแกนอาร์เรย์ครึ่งทางขวาจากองค์ประกอบตรงกลางแล้วข้ามไปที่ขั้นตอนที่ 1

• หากองค์ประกอบกลางไม่สอดคล้องกัน ให้ตรวจสอบว่าความแตกต่างระหว่างองค์ประกอบกลางกับองค์ประกอบก่อนหน้านั้นสูงกว่า 1 หรือไม่ เช่น ตรวจสอบว่า array[mid] – array[mid – 1]> 1

  • ถ้าใช่ ดังนั้น array[mid] – 1 คือองค์ประกอบที่ขาดหายไป

  • ไม่เช่นนั้น เราต้องสแกนอาร์เรย์ครึ่งซ้ายจากองค์ประกอบตรงกลางแล้วข้ามไปที่ขั้นตอนที่ 1

ตัวอย่าง

// CPP implementation of the approach
#include<bits/stdc++.h>
using namespace std;
// Shows function to return the missing element
int findMissing(int array[], int n1){
   int low = 0, high = n1 - 1;
   int mid1;
   while (high > low){
      mid1 = low + (high - low) / 2;
      // Verify if middle element is consistent
      if (array[mid1] - mid1 == array[0]){
         // Here, no inconsistency till middle elements
         // When missing element is just after
         // the middle element
         if (array[mid1 + 1] - array[mid1] > 1)
            return array[mid1] + 1;
         else{
            // Go right
            low = mid1 + 1;
         }
      }
      else{
         // Here inconsistency found
         // When missing element is just before
         // the middle element
         if (array[mid1] - array[mid1 - 1] > 1)
            return array[mid1] - 1;
         else{
            // Go left
            high = mid1 - 1;
         }
      }
   }
   // Here, no missing element found
   return -1;
}
// Driver code
int main(){
   int array[] = { -9, -8, -6, -5, -4, -3, -2, -1, 0 };
   int n1 = sizeof(array)/sizeof(array[0]);
   cout <<"The Missing Element:" <<(findMissing(array, n1));
}

ผลลัพธ์

The Missing Element:-7