Dadas dos arrays A[] y B[] que constan de N enteros positivos y una array List[][] que consta de M pares de índices, la tarea es minimizar el recuento de elementos desiguales con el mismo índice ( A i != B i ) de las dos arrays intercambiando entre cualquier par de índices dados en la array A[].
Ejemplos:
Entrada: N = 5, M = 4, A[] = {1, 5, 9, 2, 3}, B[] = {2, 4, 5, 1, 3}, Lista[][] = {{ 1, 4}, {2, 3}, {3, 5}, {2, 5}}
Salida: 1
Explicación:
array inicial A[] = {1, 5, 9, 2, 3}
Índices de intercambio (1, 4) en A[] = {2, 5, 9, 1, 3}
Intercambio de índices (2, 3) en A[] = {2, 9, 5, 1, 3}
Por lo tanto, al comparar el arreglo final A[ ] (= {2, 9, 5, 1, 3}) con la array B[] (= {2, 4, 5, 1, 3}), el único par de elementos desiguales con el mismo índice es A[2] ! = B[2] (indexación basada en 1)Entrada: N = 5, M = 4, A[] = {1, 10, 19, 6, 2}, B[] = {1, 6, 10, 2, 19}, Lista[][] = {{ 1, 4}, {2, 3}, {3, 5}, {2, 5}}
Salida: 2
Enfoque: dado que los elementos de la array A[] especificados en la lista de pares se pueden intercambiar cualquier número de veces, esos elementos se pueden considerar como un conjunto conectado con intercambios dentro de sus elementos permitidos. A continuación se detallan los pasos para implementar este enfoque:
- Recorra la array dada A[] y cree un conjunto de componentes conectados que se pueden hacer fácilmente usando el conjunto disjunto .
- Para cada elemento en B[] encuentre si el elemento correspondiente en A[] (A[i], B[i]) pertenece o no al mismo componente conexo.
- En caso afirmativo, haga A[i]=B[i] y continúe. De lo contrario, incremente el recuento de pares no coincidentes.
- Imprima el recuento de pares no coincidentes después de todos los pasos anteriores.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program for the above approach #include <bits/stdc++.h> using namespace std; int find(int par[],int x); void unionn(int par[], int a, int b); // Function that count of the mismatched // pairs in bot the array int countPairs(int A[], int B[], int N, int M, int List[][2]) { int count = 0; // Create a parent array // and initialize it int par[N + 1]; for(int i = 0; i <= N; i++) par[i] = i; // Preprocessing of the given // pairs of indices for(int i = 0; i < M; i++) { // 1-based indexing int index1 = find(par, List[i][0] - 1); int index2 = find(par, List[i][1] - 1); // If both indices doesn't belong // to same component if (index1 != index2) { // Insert the indices in // same component unionn(par, index1, index2); } } // Map to get the indices // of array A map<int, int> mp; for(int i = 0; i < N; i++) { mp[A[i]] = i; } for(int i = 0; i < N; i++) { if (A[i] != B[i]) { // If current element is not // present in array B then // count this as mismatched if(mp.find(B[i]) == mp.end()) { count++; continue; } // Get the index of the element // in array B int j = mp[B[i]]; // Check if both indices belong // to same connected component // if not increment the count if (find(par, i) != find(par, j)) count++; } } // Return answer return count; } // Function that gives the connected // component of each index int find(int par[],int x) { if (par[x] == x) return x; else return par[x] = find(par, par[x]); } // Function that creates the // connected components void unionn(int par[], int a, int b) { // Find parent of a and b // recursively a = find(par, a); b = find(par, b); if (a == b) return; // Update the parent of a par[a] = b; } // Driver Code int main() { int N = 5; int M = 4; // Given arrays A[], B[] int A[] = { 1, 5, 9, 2, 3 }; int B[] = { 2, 4, 5, 1, 3 }; // List of indices int List[][2] = { { 1, 4 }, { 2, 3 }, { 3, 5 }, { 2, 5 } }; // Function call cout << countPairs(A, B, N, M, List); return 0; } // This code is contributed by rutvik_56
Java
// Java program for the above approach import java.util.*; class GFG { // Function that count of the mismatched // pairs in bot the array public static int countPairs(int A[], int B[], int N, int M, int[][] List) { int count = 0; // Create a parent array // and initialize it int par[] = new int[N + 1]; for (int i = 0; i <= N; i++) par[i] = i; // Preprocessing of the given // pairs of indices for (int i = 0; i < M; i++) { // 1-based indexing int index1 = find(par, List[i][0] - 1); int index2 = find(par, List[i][1] - 1); // If both indices doesn't belong // to same component if (index1 != index2) { // Insert the indices in // same component union(par, index1, index2); } } // HashMap to get the indices // of array A HashMap<Integer, Integer> map = new HashMap<>(); for (int i = 0; i < N; i++) { map.put(A[i], i); } for (int i = 0; i < N; i++) { if (A[i] != B[i]) { // If current element is not // present in array B then // count this as mismatched if (!map.containsKey(B[i])) { count++; continue; } // Get the index of the element // in array B int j = map.get(B[i]); // Check if both indices belong // to same connected component // if not increment the count if (find(par, i) != find(par, j)) count++; } } // Return answer return count; } // Function that gives the connected // component of each index public static int find(int par[], int x) { if (par[x] == x) return x; else return par[x] = find(par, par[x]); } // Function that creates the // connected components public static void union(int par[], int a, int b) { // Find parent of a and b // recursively a = find(par, a); b = find(par, b); if (a == b) return; // Update the parent of a par[a] = b; } // Driver Code public static void main(String[] args) { int N = 5; int M = 4; // Given arrays A[], B[] int A[] = { 1, 5, 9, 2, 3 }; int B[] = { 2, 4, 5, 1, 3 }; // List of indices int List[][] = { { 1, 4 }, { 2, 3 }, { 3, 5 }, { 2, 5 } }; // Function Call System.out.println( countPairs(A, B, N, M, List)); } }
Python3
# Python3 program for the above approach # Function that count of the mismatched # pairs in bot the array def countPairs(A, B, N, M, List): count = 0 # Create a parent array # and initialize it par = [0] * (N + 1) for i in range(N + 1): par[i] = i # Preprocessing of the given # pairs of indices for i in range(M): # 1-based indexing index1 = find(par, List[i][0] - 1) index2 = find(par, List[i][1] - 1) # If both indices doesn't belong # to same component if(index1 != index2): # Insert the indices in # same component union(par, index1, index2) # HashMap to get the indices # of array A map = {} for i in range(N): map[A[i]] = i for i in range(N): if(A[i] != B[i]): # If current element is not # present in array B then # count this as mismatched if(B[i] not in map.keys()): count += 1 continue # Get the index of the element # in array B j = map[B[i]] # Check if both indices belong # to same connected component # if not increment the count if(find(par, i) != find(par, j)): count += 1 # Return answer return count # Function that gives the connected # component of each index def find(par, x): if(par[x] == x): return x else: par[x] = find(par, par[x]) return par[x] # Function that creates the # connected components def union(par, a, b): # Find parent of a and b # recursively a = find(par, a) b = find(par, b) if(a == b): return # Update the parent of a par[a] = b # Driver Code N = 5 M = 4 # Given arrays A[], B[] A = [ 1, 5, 9, 2, 3 ] B = [ 2, 4, 5, 1, 3 ] # List of indices List = [ [ 1, 4 ], [ 2, 3 ], [ 3, 5 ], [ 2, 5 ] ] # Function call print(countPairs(A, B, N, M, List)) # This code is contributed by Shivam Singh
C#
// C# program for the above approach using System; using System.Collections.Generic; class GFG{ // Function that count of the mismatched // pairs in bot the array public static int countPairs(int[] A, int[] B, int N, int M, int[, ] List) { int count = 0; // Create a parent array // and initialize it int[] par = new int[N + 1]; for (int i = 0; i <= N; i++) par[i] = i; // Preprocessing of the given // pairs of indices for (int i = 0; i < M; i++) { // 1-based indexing int index1 = find(par, List[i, 0] - 1); int index2 = find(par, List[i, 1] - 1); // If both indices doesn't belong // to same component if (index1 != index2) { // Insert the indices in // same component union(par, index1, index2); } } // Dictionary to get the indices // of array A Dictionary<int, int> map = new Dictionary<int, int>(); for (int i = 0; i < N; i++) { if (map.ContainsKey(A[i])) map[A[i]] = i; else map.Add(A[i], i); } for (int i = 0; i < N; i++) { if (A[i] != B[i]) { // If current element is not // present in array B then // count this as mismatched if (!map.ContainsKey(B[i])) { count++; continue; } // Get the index of the element // in array B int j = map[B[i]]; // Check if both indices belong // to same connected component // if not increment the count if (find(par, i) != find(par, j)) count++; } } // Return answer return count; } // Function that gives the connected // component of each index public static int find(int[] par, int x) { if (par[x] == x) return x; else return par[x] = find(par, par[x]); } // Function that creates the // connected components public static void union(int[] par, int a, int b) { // Find parent of a and b // recursively a = find(par, a); b = find(par, b); if (a == b) return; // Update the parent of a par[a] = b; } // Driver Code public static void Main(String[] args) { int N = 5; int M = 4; // Given arrays []A, []B int[] A = {1, 5, 9, 2, 3}; int[] B = {2, 4, 5, 1, 3}; // List of indices int[, ] List = {{1, 4}, {2, 3}, {3, 5}, {2, 5}}; // Function Call Console.WriteLine(countPairs(A, B, N, M, List)); } } // This code is contributed by shikhasingrajput
Javascript
<script> // Javascript program for the above approach // Function that count of the mismatched // pairs in bot the array function countPairs(A, B, N, M, List) { var count = 0; // Create a parent array // and initialize it var par = Array(N+1); for(var i = 0; i <= N; i++) par[i] = i; // Preprocessing of the given // pairs of indices for(var i = 0; i < M; i++) { // 1-based indexing var index1 = find(par, List[i][0] - 1); var index2 = find(par, List[i][1] - 1); // If both indices doesn't belong // to same component if (index1 != index2) { // Insert the indices in // same component unionn(par, index1, index2); } } // Map to get the indices // of array A var mp = new Map(); for(var i = 0; i < N; i++) { mp.set(A[i], i); } for(var i = 0; i < N; i++) { if (A[i] != B[i]) { // If current element is not // present in array B then // count this as mismatched if(!mp.has(B[i])) { count++; continue; } // Get the index of the element // in array B var j = mp.get(B[i]); // Check if both indices belong // to same connected component // if not increment the count if (find(par, i) != find(par, j)) count++; } } // Return answer return count; } // Function that gives the connected // component of each index function find(par,x) { if (par[x] == x) return x; else return par[x] = find(par, par[x]); } // Function that creates the // connected components function unionn(par, a, b) { // Find parent of a and b // recursively a = find(par, a); b = find(par, b); if (a == b) return; // Update the parent of a par[a] = b; } // Driver Code var N = 5; var M = 4; // Given arrays A[], B[] var A = [1, 5, 9, 2, 3]; var B = [2, 4, 5, 1, 3]; // List of indices var List = [ [ 1, 4 ], [ 2, 3 ], [ 3, 5 ], [ 2, 5 ] ]; // Function call document.write( countPairs(A, B, N, M, List)); // This code is contributed by itsok. </script>
1
Complejidad temporal: O(N + M)
Espacio auxiliar: O(N)
Publicación traducida automáticamente
Artículo escrito por hemanthswarna1506 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA