使两个数组相同的最小交换 · GeeksForGeeks 中文系列教程

# 使两个数组相同的最小交换 > 原文： [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。