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-1 với một giá trị xuất hiện hai lần trong mảng. Nhiệm vụ của chúng ta là tìm phần tử lặp lại duy nhất trong một mảng được sắp xếp có kích thước n .
Hãy lấy một ví dụ để hiểu vấn đề,
Đầu vào
arr[] = {1, 2, 3, 4, 5, 5, 6, 7} Đầu ra
5
Phương pháp tiếp cận giải pháp
Một cách tiếp cận đơn giản để giải quyết vấn đề là sử dụng tìm kiếm tuyến tính và kiểm tra xem arr [i] và arr [i + 1] có cùng giá trị hay không. Trong trường hợp này, hãy trả về arr [i] là giá trị được lặp lại.
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 findRepeatingValueArr(int arr[], int N){
for(int i = 0; i < N; i++){
if(arr[i] == arr[i+1])
return (arr[i]);
}
return -1;
}
int main(){
int arr[] = {1, 2, 3, 4, 4, 5, 6};
int N = sizeof(arr)/sizeof(arr[0]);
cout<<"The repeating value in the array is "<<findRepeatingValueArr(arr, N);
return 0;
} Đầu ra
The repeating value in the array is 4
Một cách tiếp cận khác để giải quyết vấn đề là sử dụng thuật toán tìm kiếm nhị phân để tìm phần tử xuất hiện hai lần ở chỉ mục giữa. Nếu giá trị chỉ số giữa lặp lại chính nó thì hãy in nó. Nếu nó không ở vị trí chỉ mục, hãy di chuyển qua mảng con bên phải, nếu không thì sẽ đi qua mảng con bên trá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 <bits/stdc++.h>
using namespace std;
int findRepeatingValueArr(int arr[], int s, int e){
if (s > e)
return -1;
int mid = (s + e) / 2;
if (arr[mid] != mid + 1){
if (mid > 0 && arr[mid]==arr[mid-1])
return arr[mid];
return arr[findRepeatingValueArr(arr, s, mid-1)];
}
return arr[findRepeatingValueArr(arr, mid+1, e)];
}
int main(){
int arr[] = {1, 2, 3, 4, 5, 6, 6, 7, 8, 9};
int n = sizeof(arr) / sizeof(arr[0]);
cout<<"The repeating value in the array is "<<findRepeatingValueArr(arr, 0, n-1);;
return 0;
} Đầu ra
The repeating value in the array is 6