Giả sử chúng ta có một mảng A chưa được sắp xếp và hai số x và y. Ta phải tìm khoảng cách nhỏ nhất giữa x và y trong A. Mảng cũng có thể chứa các phần tử trùng lặp. Vì vậy, nếu mảng là A =[2, 5, 3, 5, 4, 4, 2, 3], x =3 và y =2, thì khoảng cách nhỏ nhất giữa 3 và 2 chỉ là 1.
Để giải quyết vấn đề này, chúng ta phải làm theo các bước sau,
- Duyệt mảng từ trái sang phải và dừng lại nếu tìm thấy x hoặc y. Sau đó, lưu trữ chỉ số của vị trí đó vào trước
- Bây giờ, hãy duyệt qua mảng sau chỉ số trước đó, nếu phần tử có chỉ mục hiện tại i khớp với x hoặc y, thì hãy kiểm tra xem nó có khác với A [trước] không, nếu khác thì cập nhật chỉ mục tối thiểu nếu cần , nếu điều đó khác, thì hãy cập nhật trước như trước:=i
Ví dụ
#include<iostream>
using namespace std;
int findMinDistance(int A[], int n, int x, int y) {
int i = 0;
int distance = INT_MAX;
int prev_index;
for (i = 0; i < n; i++) {
if (A[i] == x || A[i] == y) {
prev_index = i;
break;
}
}
while (i < n) {
if (A[i] == x || A[i] == y) {
if ( A[prev_index] != A[i] && (i - prev_index) < distance ){
distance = i - prev_index;
prev_index = i;
} else
prev_index = i;
}
i++;
}
return distance;
}
int main() {
int arr[] = {2, 5, 3, 5, 4, 4, 2, 3};
int n = sizeof(arr) / sizeof(arr[0]);
int x = 3;
int y = 2;
cout << "Minimum distance between " << x << " and " << y << " is: "<< findMinDistance(arr, n, x, y);
} Đầu ra
Minimum distance between 3 and 2 is: 1