ในปัญหานี้ เราได้รับ arr[] ขนาด N ที่มีค่าตั้งแต่ 1 ถึง N โดยมีค่าหายไปหนึ่งค่าในอาร์เรย์ งานของเราคือ ค้นหาเฉพาะตัวเลขที่ขาดหายไปในอาร์เรย์ที่จัดเรียง .
มาดูตัวอย่างเพื่อทำความเข้าใจปัญหากัน
ป้อนข้อมูล
arr[] = {1, 2, 3, 5, 6, 7} ผลผลิต
4
แนวทางการแก้ปัญหา
วิธีแก้ปัญหาอย่างง่ายคือการสำรวจอาร์เรย์ที่จัดเรียงเป็นเส้นตรง แล้วตรวจสอบค่าที่หายไปโดยใช้ข้อเท็จจริงว่า arr[i] =(i + 1)
ตัวอย่างที่ 1
โปรแกรมเพื่อแสดงการทำงานของโซลูชันของเรา
#include <iostream>
using namespace std;
int findMissingValArray(int arr[], int N){
for(int i = 0; i < N; i++){
if(arr[i] != (i+1))
return (i+1);
}
return -1;
}
int main(){
int arr[] = {1, 2, 3, 4, 6};
int N = sizeof(arr)/sizeof(arr[0]);
cout<<"The missing value from the array is "<<findMissingValArray(arr, N);
return 0;
} ผลลัพธ์
The missing value from the array is 5
อีกวิธีในการแก้ปัญหาคือการใช้การค้นหาแบบไบนารีและตรวจสอบค่าที่ช่วงกลาง หากค่าที่ mid คือ mid+1 และค่าที่ (mid - 1) คือ (mid) เราจะข้าม subarray ด้านซ้ายและในทางกลับกัน
ตัวอย่างที่ 2
โปรแกรมเพื่อแสดงการทำงานของโซลูชันของเรา
#include <iostream>
using namespace std;
int findMissingValArray(int arr[], int N){
int s = 0, e = N - 1;
while (s <= e) {
int mid = (s + e) / 2;
if (arr[mid] != mid + 1 && arr[mid - 1] == mid)
return (mid + 1);
if (arr[mid] != (mid + 1))
e = (mid - 1);
else
s = (mid + 1);
}
return -1;
}
int main(){
int arr[] = {1, 2, 3, 4, 6};
int N = sizeof(arr)/sizeof(arr[0]);
cout<<"The missing value from the array is "<<findMissingValArray(arr, N);
return 0;
} ผลลัพธ์
The missing value from the array is 5
