ในปัญหานี้ เราได้รับ arr[] ขนาด n งานของเราคือ ค้นหาหมายเลขที่ขาดหายไปในช่วง .
อาร์เรย์ประกอบด้วยค่าทั้งหมดตั้งแต่ค่าที่น้อยที่สุดถึง (น้อยที่สุด + n) องค์ประกอบของช่วงหายไปจากอาร์เรย์ และเราต้องหาค่าที่ขาดหายไปนี้
มาดูตัวอย่างเพื่อทำความเข้าใจปัญหากัน
ป้อนข้อมูล
arr[] = {4, 8, 5, 7} ผลผลิต
6
แนวทางการแก้ปัญหา
วิธีแก้ปัญหาง่ายๆ คือการค้นหาองค์ประกอบที่ขาดหายไปโดยจัดเรียงอาร์เรย์ จากนั้นค้นหาองค์ประกอบแรกของช่วงโดยเริ่มจากค่าต่ำสุดซึ่งไม่มีอยู่ในอาร์เรย์ แต่มีอยู่ในช่วง
วิธีนี้เป็นวิธีที่ไร้เดียงสาและจะแก้ปัญหาคือความซับซ้อนของเวลา O(n log n)
อีกแนวทางหนึ่งในการแก้ปัญหาในเวลาอันสั้นคือการใช้ XOR ของค่าของอาร์เรย์และช่วง เราจะค้นหา XOR ของค่าทั้งหมดในช่วงและค้นหา XOR ของค่าทั้งหมดในอาร์เรย์ด้วย XOR ของค่าทั้งสองนี้จะเป็นค่าที่หายไปของเรา
ตัวอย่าง
โปรแกรมเพื่อแสดงการทำงานของโซลูชันของเรา
#include <bits/stdc++.h>
using namespace std;
int findMissingNumArr(int arr[], int n){
int arrMin = *min_element(arr, arr+n);
int numXor = 0;
int rangeXor = arrMin;
for (int i = 0; i < n; i++) {
numXor ^= arr[i];
arrMin++;
rangeXor ^= arrMin;
}
return numXor ^ rangeXor;
}
int main(){
int arr[] = { 5, 7, 4, 8, 9};
int n = sizeof(arr)/sizeof(arr[0]);
cout<<"The missing value in the array is "<<findMissingNumArr(arr, n);
return 0;
} ผลลัพธ์
The missing value in the array is 6
