หาความแตกต่างความเข้ากันได้ระหว่างสองอาร์เรย์ใน C++

พิจารณา 2 เพื่อนต้องการทดสอบความผูกพัน จะตรวจสอบว่าพวกเขาเข้ากันได้มากแค่ไหน ได้รับตัวเลข n ตัวเลข 1..n พวกเขาถูกขอให้จัดอันดับตัวเลข ต้องหาความแตกต่างความเข้ากันได้ (Compatibility Difference) ระหว่างพวกเขา ซึ่งก็คือจำนวน Mismatch ในการจัดอันดับสัมพัทธ์ของหนังสือ/ภาพยนตร์เดียวกันที่ทั้งคู่ให้มา

เช่น A = [3, 1, 2, 4, 5], B = [3, 2, 4, 1, 5] ผลลัพธ์คือ 2 ความแตกต่างคือ 2 เพราะคนแรกจัดอันดับ 1 ก่อน 2 และ 4 แต่คนที่สองจัดอันดับ 1 หลัง 2 และ 4

วิธีแก้: ท่องทั้งสองอาร์เรย์ ถ้าองค์ประกอบปัจจุบันเท่ากัน ไม่ทำอะไร หาตำแหน่งถัดไปของ A และ B ให้เป็น j ย้าย B[j] ไป B[i] ทีละตัว

ตัวอย่างโค้ด

#include <iostream>
using namespace std;

int getArrayDiff(int A[], int B[], int n) {
    int result = 0;
    for (int i = 0; i < n; i++) {
        if (A[i] != B[i]) {
            int j = i + 1;
            while (A[i] != B[j])
                j++;
            while (j != i) {
                swap(B[j], B[j - 1]);
                j--;
                result++;
            }
        }
    }
    return result;
}

int main() {
    int A[] = { 3, 1, 2, 4, 5 };
    int B[] = { 3, 2, 4, 1, 5 };
    int n = sizeof(A) / sizeof(A[0]);
    cout << "Compatibility difference: " << getArrayDiff(A, B, n);
}

ผลลัพธ์

Compatibility difference: 2