หาความห่างขั้นต่ำระหว่างสองตัวเลขในอาร์เรย์ใน C++

สมมติว่ามีอาร์เรย์ A แบบไม่เรียงลำดับ และตัวเลขสองตัว x และ y เราต้องหาความห่างขั้นต่ำระหว่าง x และ y ใน A อาร์เรย์อาจมีองค์ประกอบซ้ำได้ ดังนั้นถ้าอาร์เรย์คือ A = [2, 5, 3, 5, 4, 4, 2, 3], x = 3 และ y = 2 ความห่างขั้นต่ำระหว่าง 3 และ 2 คือเพียง 1

เพื่อแก้ปัญหานี้ เราต้องทำตามขั้นตอนเหล่านี้:

• เดินทางผ่านอาร์เรย์จากซ้ายไปขวา และหยุดถ้า x หรือ y ถูกพบ แล้วเก็บดัชนีของตำแหน่งนั้นไว้ใน prev
• ตอนนี้เดินทางผ่านอาร์เรย์หลังจากดัชนี prev หากองค์ประกอบที่มีดัชนีปัจจุบัน i ตรงกับ x หรือ y ให้ตรวจสอบว่ามันต่างจาก A[prev] หรือไม่ หากต่างกัน ให้อัปเดตดัชนีขั้นต่ำหากจำเป็น หากต่างกัน ให้อัปเดต 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