ในปัญหานี้ เราได้รับอาร์เรย์ 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
อีกวิธีหนึ่งในการแก้ปัญหาคือการใช้ binary search และตรวจสอบค่าที่ mid หากค่าที่ mid คือ mid+1 และค่าที่ (mid - 1) คือ (mid) เราจะเดินทางไปยัง left 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
