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

แนวคิด

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

อินพุต

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 หายไปจากอาร์เรย์แรก

วิธีการ

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

เราสามารถใช้วิธีที่มีประสิทธิภาพอีกวิธีหนึ่งซึ่งอิงจาก binary search approach เราทำตามอัลกอริทึมด้านล่างซึ่งอธิบายทีละขั้นตอน −

• เริ่ม binary search ในอาร์เรย์ที่ใหญ่กว่า และได้ mid เป็น (low + high) / 2
• พบว่าถ้าค่าจากทั้งสองอาร์เรย์เท่ากัน missing element ต้องอยู่ในส่วนขวา จึงตั้ง low เป็น mid
• มิฉะนั้น ตั้ง high เป็น mid เพราะ missing element ต้องอยู่ในส่วนซ้ายของอาร์เรย์ที่ใหญ่กว่า ถ้า mid elements ไม่เท่ากัน
• เราต้องจัดการ special case แยกต่างหาก เพราะสำหรับ single element และ zero element array องค์ประกอบเดี่ยวเองจะเป็น missing element

สังเกตได้ว่าถ้า first element เองไม่เท่ากัน องค์ประกอบนั้นจะเป็น missing element

ตัวอย่างโค้ด

// โปรแกรม C++ เพื่อหาองค์ประกอบที่หายไปจากอาร์เรย์เดียวกัน // (ยกเว้นหนึ่ง missing element) #include <bits/stdc++.h> using namespace std; // ฟังก์ชันแสดงการกำหนด missing element อิงจาก binary // search approach arrA[] มีขนาดใหญ่กว่าและ // Q คือขนาดของมัน arrA[] และ arrB[] ถูกสมมติว่า // อยู่ในลำดับเดียวกัน int findMissingUtil(int arrA[], int arrB[], int Q){    // พิจารณา special case สำหรับองค์ประกอบเดียวที่    // หายไปในอาร์เรย์ที่สอง    if (Q == 1)       return arrA[0];    // พิจารณา special case สำหรับ first element missing    if (arrA[0] != arrB[0])       return arrA[0];    // ใช้เริ่มต้น current corner points    int low = 0, high = Q - 1;    // Iterate จนกว่า low < high    while (low < high){       int mid = (low + high) / 2;       // สังเกตได้ว่าถ้าองค์ประกอบที่ mid indices เท่ากัน       // แล้วไปที่ right subarray       if (arrA[mid] == arrB[mid])          low = mid;       else          high = mid;          // ดังนั้นถ้า low, high กลายเป็น contiguous ให้ break       if (low == high - 1)       break;    }    // ตอนนี้ missing element จะอยู่ที่ high index ของ    // อาร์เรย์ที่ใหญ่กว่า    return arrA[high]; } // ฟังก์ชันนี้หลักทำ basic error checking // และเรียก 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"; } // โค้ดหลัก 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