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

พิจารณาว่ามีเพื่อนสองคนและตอนนี้พวกเขาต้องการทดสอบความสัมพันธ์ของพวกเขา ดังนั้นพวกเขาจะตรวจสอบว่าเข้ากันได้มากแค่ไหน ให้ตัวเลข n, หมายเลขจาก 1..n. และขอให้พวกเขาจัดอันดับตัวเลข พวกเขาต้องหาความเข้ากันได้ระหว่างพวกเขา ความแตกต่างของความเข้ากันได้นั้นเป็นจำนวนที่ไม่ตรงกันในการจัดอันดับที่เกี่ยวข้องของภาพยนตร์เรื่องเดียวกันที่ได้รับจากพวกเขา ดังนั้นถ้า A =[3, 1, 2, 4, 5] และ B =[3, 2, 4, 1, 5] ผลลัพธ์จะเป็น 2 ความแตกต่างของความเข้ากันได้คือ 2 เช่นเดียวกับภาพยนตร์อันดับ 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