Trong bài toán này, chúng ta được cung cấp một arr [] có kích thước N chứa các giá trị từ 1 đến N với một giá trị bị thiếu trong mảng. Nhiệm vụ của chúng tôi là tìm số còn thiếu duy nhất trong một mảng đã sắp xếp .
Hãy lấy một ví dụ để hiểu vấn đề,
Đầu vào
arr[] = {1, 2, 3, 5, 6, 7} Đầu ra
4
Phương pháp tiếp cận giải pháp
Một giải pháp đơn giản cho vấn đề là duyệt theo tuyến tính mảng đã sắp xếp. Và sau đó kiểm tra giá trị bị thiếu bằng cách sử dụng thực tế là arr [i] =(i + 1).
Ví dụ 1
Chương trình minh họa hoạt động của giải pháp của chúng tôi
#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;
} Đầu ra
The missing value from the array is 5
Một cách tiếp cận khác để giải quyết vấn đề là sử dụng tìm kiếm nhị phân và kiểm tra giá trị ở giữa. Nếu giá trị ở giữa là giữa + 1 và giá trị tại (giữa - 1) là (giữa) thì chúng ta sẽ đi ngang qua mảng con bên trái và ngược lại.
Ví dụ 2
Chương trình minh họa hoạt động của giải pháp của chúng tôi
#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;
} Đầu ra
The missing value from the array is 5