Given two arrays that have the same values but in a different order, we need to make a second array the same as a first array using the minimum number of swaps.
Examples:
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}
This problem can be solved by modifying the array B. We save the index of array A elements in array B i.e. if ith element of array A is at jth position in array B, then we will make arrB[i] = j
For above given example, modified array B will be, arrB = {3, 1, 0, 2}. This modified array represents the distribution of array A element in array B and our goal is to sort this modified array in a minimum number of swaps because after sorting only array B element will be aligned with array A elements.
So we count these swaps in a modified array and that will be our final answer.
Please see the below code for a better understanding.
- C++
- Java
- Python3
- C#
- Javascript
// 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;
}
Output:
2