สมมติว่าเรามีอาร์เรย์ A ที่ไม่เรียงลำดับหนึ่งตัว และตัวเลข x และ y สองตัว เราต้องหาระยะห่างขั้นต่ำระหว่าง x และ y ใน A อาร์เรย์ยังสามารถมีองค์ประกอบที่ซ้ำกันได้ ดังนั้น หากอาร์เรย์คือ A =[2, 5, 3, 5, 4, 4, 2, 3], x =3 และ y =2 ดังนั้นระยะห่างขั้นต่ำระหว่าง 3 ถึง 2 จะเท่ากับ 1
เพื่อแก้ปัญหานี้ เราต้องทำตามขั้นตอนเหล่านี้
- สำรวจอาร์เรย์จากซ้ายไปขวาและหยุดหากพบ x หรือ y จากนั้นเก็บดัชนีของตำแหน่งนั้นไว้ก่อนหน้า
- ตอนนี้สำรวจอาร์เรย์หลังดัชนีก่อนหน้า หากองค์ประกอบที่มีดัชนีปัจจุบัน i ตรงกับ x หรือ y ให้ตรวจสอบว่าแตกต่างจาก A[ก่อนหน้า] หรือไม่ หากแตกต่างกัน ให้อัปเดตดัชนีขั้นต่ำ หากจำเป็น หากแตกต่างออกไป ให้อัปเดต prev เป็น prev :=i
ตัวอย่าง
#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);
} ผลลัพธ์
Minimum distance between 3 and 2 is: 1
