Dadas dos arrays que tienen los mismos valores pero en un orden diferente y sin elementos duplicados, necesitamos hacer una segunda array igual a la primera utilizando la cantidad mínima de intercambios.
Ejemplos:
Entrada: arrA[] = {3, 6, 4, 8},
arrB[] = {4, 6, 8, 3}
Salida: 2
Explicación: podemos hacer que arrB sea igual que arrA en 2 intercambios que se muestran a continuación, intercambiar 4 con 8,
arrB = {8, 6, 4, 3} intercambiar 8 con 3, arrB = {3, 6, 4, 8}
Este problema se puede resolver modificando la array B. Guardamos el índice de los elementos de la array A en la array B, es decir, si el i-ésimo elemento de la array A está en la j-ésima posición en la array B, entonces haremos arrB[i] = j Para lo
anterior ejemplo, la array B modificada será arrB = {3, 1, 0, 2}. Esta array modificada representa la distribución del elemento de la array A en la array B y nuestro objetivo es ordenar esta array modificada en un número mínimo de intercambios porque después de ordenar solo el elemento de la array B se alineará con los elementos de la array A.
Ahora se puede encontrar el número de intercambios mínimos para ordenar una array visualizando el problema como un gráfico , este problema ya se explicó en el artículo anterior .
Así que contamos estos intercambios en una array modificada y esa será nuestra respuesta final.
Por favor, consulte el siguiente código para una mejor comprensión.
C++
// 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; */
// returning 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;
}
Java
// Java program to make an array same to another
// using minimum number of swap
import java.io.*;
import java.util.*;
// 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/
class GFG
{
static 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
ArrayList<ArrayList<Integer>> arrPos = new ArrayList<ArrayList<Integer>>();
for (int i = 0; i < n; i++)
{
arrPos.add(new ArrayList<Integer>(Arrays.asList(arr[i],i)));
}
// Sort the array by array element values to
// get right position of every element as second
// element of pair.
Collections.sort(arrPos, new Comparator<ArrayList<Integer>>() {
@Override
public int compare(ArrayList<Integer> o1, ArrayList<Integer> o2) {
return o1.get(0).compareTo(o2.get(0));
}
});
// To keep track of visited elements. Initialize
// all elements as not visited or false.
boolean[] vis = new boolean[n];
// 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.get(i).get(1) == 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] = true;
// move to next node
j = arrPos.get(j).get(1);
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
static 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<Integer, Integer> mp
= new HashMap<Integer, Integer>();
for (int i = 0; i < n; i++)
{
mp.put(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.get(a[i]);
/* We can uncomment this section to print modified
b array
for (int i = 0; i < N; i++)
cout << b[i] << " ";
cout << endl; */
// returning minimum swap for sorting in modified
// array B as final answer
return minSwapsToSort(b, n);
}
// Driver code
public static void main (String[] args)
{
int a[] = {3, 6, 4, 8};
int b[] = {4, 6, 8, 3};
int n = a.length;
System.out.println( minSwapToMakeArraySame(a, b, n));
}
}
// This code is contributed by avanitrachhadiya2155
Python3
# Python3 program to make
# an array same to another
# using minimum number of swap
# 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/
def minSwapsToSort(arr, n):
# Create an array of pairs
# where first element is
# array element and second
# element is position of
# first element
arrPos = [[0 for x in range(2)]
for y in range(n)]
for i in range(n):
arrPos[i][0] = arr[i]
arrPos[i][1] = i
# Sort the array by array
# element values to get right
# position of every element
# as second element of pair.
arrPos.sort()
# To keep track of visited
# elements. Initialize all
# elements as not visited
# or false.
vis = [False] * (n)
# Initialize result
ans = 0
# Traverse array elements
for i in range(n):
# Already swapped and corrected or
# already present at correct pos
if (vis[i] or arrPos[i][1] == i):
continue
# Find out the number of node in
# this cycle and add in ans
cycle_size = 0
j = i
while (not vis[j]):
vis[j] = 1
# Move to next node
j = arrPos[j][1]
cycle_size+= 1
# 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
def minSwapToMakeArraySame(a, b, n):
# map to store position
# of elements in array B
# we basically store
# element to index mapping.
mp = {}
for i in range(n):
mp[b[i]] = i
# now we're storing position
# of array A elements
# in array B.
for i in range(n):
b[i] = mp[a[i]]
# Returning minimum swap
# for sorting in modified
# array B as final answer
return minSwapsToSort(b, n)
# Driver code
if __name__ == "__main__":
a = [3, 6, 4, 8]
b = [4, 6, 8, 3]
n = len(a)
print(minSwapToMakeArraySame(a, b, n))
# This code is contributed by Chitranayal
C#
// C# program to make an array same to another
// using minimum number of swap
using System;
using System.Collections.Generic;
using System.Linq;
// 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/
public class GFG{
static 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
List<List<int>> arrPos = new List<List<int>>();
for (int i = 0; i < n; i++)
{
arrPos.Add(new List<int>(){arr[i],i});
}
// Sort the array by array element values to
// get right position of every element as second
// element of pair.
arrPos=arrPos.OrderBy(x => x[0]).ToList();
// To keep track of visited elements. Initialize
// all elements as not visited or false.
bool[] vis = new bool[n];
Array.Fill(vis,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][1] == 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] = true;
// move to next node
j = arrPos[j][1];
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
static int minSwapToMakeArraySame(int[] a, int[] b, int n)
{
Dictionary<int,int> mp = new Dictionary<int,int>();
for (int i = 0; i < n; i++)
{
mp.Add(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; */
// returning minimum swap for sorting in modified
// array B as final answer
return minSwapsToSort(b, n);
}
// Driver code
static public void Main (){
int[] a = {3, 6, 4, 8};
int[] b = {4, 6, 8, 3};
int n = a.Length;
Console.WriteLine( minSwapToMakeArraySame(a, b, n));
}
}
// This code is contributed by rag2127
Javascript
<script>
// JavaScript program to make an array same to another
// using minimum number of swap
// 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/
*/
function minSwapsToSort(arr,n)
{
// Create an array of pairs where first
// element is array element and second element
// is position of first element
let arrPos = [];
for (let i = 0; i < n; i++)
{
arrPos.push([arr[i],i]);
}
// Sort the array by array element values to
// get right position of every element as second
// element of pair.
arrPos.sort(function(a,b){return a[0]-b[0];});
// To keep track of visited elements. Initialize
// all elements as not visited or false.
let vis = new Array(n);
for(let i=0;i<n;i++)
{
vis[i]=false;
}
// Initialize result
let ans = 0;
// Traverse array elements
for (let i = 0; i < n; i++)
{
// already swapped and corrected or
// already present at correct pos
if (vis[i] || arrPos[i][1] == i)
continue;
// find out the number of node in
// this cycle and add in ans
let cycle_size = 0;
let j = i;
while (!vis[j])
{
vis[j] = true;
// move to next node
j = arrPos[j][1];
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
function minSwapToMakeArraySame(a,b,n)
{
// map to store position of elements in array B
// we basically store element to index mapping.
let mp = new Map();
for (let i = 0; i < n; i++)
{
mp.set(b[i], i);
}
// now we're storing position of array A elements
// in array B.
for (let i = 0; i < n; i++)
b[i] = mp.get(a[i]);
/* We can uncomment this section to print modified
b array
for (int i = 0; i < N; i++)
cout << b[i] << " ";
cout << endl; */
// returning minimum swap for sorting in modified
// array B as final answer
return minSwapsToSort(b, n);
}
// Driver code
let a=[3, 6, 4, 8];
let b=[4, 6, 8, 3];
let n = a.length;
document.write( minSwapToMakeArraySame(a, b, n));
// This code is contributed by ab2127
</script>
Producción:
2
Complejidad de Tiempo: O(n log n)
Espacio Auxiliar: O(n)
Este artículo es una contribución de Utkarsh Trivedi . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu artículo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA