# 使兩個數組相同的最小交換 > 原文： [https://www.geeksforgeeks.org/minimum-swaps-to-make-two-array-identical/](https://www.geeksforgeeks.org/minimum-swaps-to-make-two-array-identical/) 給定兩個具有相同值但順序不同的數組，我們需要使用最少的交換次數使第二個數組與第一個數組相同。 示例： ``` Input : arrA[] = {3, 6, 4, 8}, arrB[] = {4, 6, 8, 3} Output : 2 we can make arrB to same as arrA in 2 swaps which are shown below, swap 4 with 8, arrB = {8, 6, 4, 3} swap 8 with 3, arrB = {3, 6, 4, 8} ``` 這個問題可以通過修改數組 B 來解決。我們將數組 A 的元素的索引保存在數組 B 中，即如果數組 A 的第 i 個元素在數組 B 中的第 j 個位置，則將使 arrB [i] = j 對于上面給出的示例，修改后的數組 B 將為 arrB = {3，1，0，2}。 此修改后的數組表示數組 B 中的數組 A 元素的分布，我們的目標是以最少的交換次數對此修改后的數組進行排序，因為排序后僅數組 B 元素將與數組 A 元素對齊。 現在可以通過將問題可視化為圖形來找到用于排序數組的[最小交換數，該問題已在](https://www.geeksforgeeks.org/minimum-number-swaps-required-sort-array/)[先前的文章](https://www.geeksforgeeks.org/minimum-number-swaps-required-sort-array/)中進行了解釋。 因此，我們將這些交換數計入修改后的數組中，這將是我們的最終答案。 請參見以下代碼，以更好地理解。 ``` // C++ program to make an array same to another // using minimum number of swap #include <bits/stdc++.h> using namespace std; // Function returns the minimum number of swaps // required to sort the array // This method is taken from below post // https://www.geeksforgeeks.org/minimum-number-swaps-required-sort-array/ int minSwapsToSort(int arr[], int n) { ????// Create an array of pairs where first ????// element is array element and second element ????// is position of first element ????pair<int, int> arrPos[n]; ????for (int i = 0; i < n; i++) ????{ ????????arrPos[i].first = arr[i]; ????????arrPos[i].second = i; ????} ????// Sort the array by array element values to ????// get right position of every element as second ????// element of pair. ????sort(arrPos, arrPos + n); ????// To keep track of visited elements. Initialize ????// all elements as not visited or false. ????vector<bool> vis(n, false); ????// Initialize result ????int ans = 0; ????// Traverse array elements ????for (int i = 0; i < n; i++) ????{ ????????// already swapped and corrected or ????????// already present at correct pos ????????if (vis[i] || arrPos[i].second == i) ????????????continue; ????????// find out the number of? node in ????????// this cycle and add in ans ????????int cycle_size = 0; ????????int j = i; ????????while (!vis[j]) ????????{ ????????????vis[j] = 1; ????????????// move to next node ????????????j = arrPos[j].second; ????????????cycle_size++; ????????} ????????// Update answer by adding current cycle. ????????ans += (cycle_size - 1); ????} ????// Return result ????return ans; } // method returns minimum number of swap to make // array B same as array A int minSwapToMakeArraySame(int a[], int b[], int n) { ????// map to store position of elements in array B ????// we basically store element to index mapping. ????map<int, int> mp; ????for (int i = 0; i < n; i++) ????????mp[b[i]] = i; ????// now we're storing position of array A elements ????// in array B. ????for (int i = 0; i < n; i++) ????????b[i] = mp[a[i]]; ????/* We can uncomment this section to print modified ??????b array ????for (int i = 0; i < N; i++) ????????cout << b[i] << " "; ????cout << endl; */ ????// returing minimum swap for sorting in modified ????// array B as final answer ????return minSwapsToSort(b, n); } //? Driver code to test above methods int main() { ????int a[] = {3, 6, 4, 8}; ????int b[] = {4, 6, 8, 3}; ????int n = sizeof(a) / sizeof(int); ????cout << minSwapToMakeArraySame(a, b, n); ????return 0; } ``` 輸出： ``` 2 ``` 本文由 [**Utkarsh Trivedi**](https://in.linkedin.com/in/utkarsh-trivedi-253069a7) 貢獻。 如果您喜歡 GeeksforGeeks 并希望做出貢獻，則還可以使用 [tribution.geeksforgeeks.org](http://www.contribute.geeksforgeeks.org) 撰寫文章，或將您的文章郵寄至 tribution@geeksforgeeks.org。 查看您的文章出現在 GeeksforGeeks 主頁上，并幫助其他 Geeks。