ในปัญหานี้ เราได้รับอาร์เรย์ arr[] ขนาด n ภารกิจของเราคือ หาตัวเลขที่หายไปหนึ่งตัวในช่วง
อาร์เรย์ประกอบด้วยค่าทั้งหมดตั้งแต่ค่าน้อยที่สุดถึง (ค่าน้อยที่สุด + n) องค์ประกอบหนึ่งของช่วงหายไปจากอาร์เรย์ และเราต้องหาค่าที่หายไปนี้
มาดูตัวอย่างเพื่อเข้าใจปัญหา
อินพุต
arr[] = {4, 8, 5, 7}
เอาต์พุต
6
วิธีการแก้ปัญหา
วิธีแก้ปัญหาแบบง่ายคือการค้นหาองค์ประกอบที่หายไปโดยการจัดเรียงอาร์เรย์แล้วหาองค์ประกอบแรกของช่วงเริ่มจากค่าน้อยที่สุดซึ่งไม่อยู่ในอาร์เรย์แต่อยู่ในช่วง
วิธีนี้เป็นวิธีที่ naive และจะแก้ปัญหาในเวลา 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
