Dada una array arr[] que consta de N enteros positivos distintos, la tarea es encontrar el número mínimo de elementos necesarios para intercambiar para minimizar la suma de la diferencia absoluta de cada par de elementos adyacentes .
Ejemplos:
Entrada: arr[] = {8, 50, 11, 2}
Salida: 2
Explicación:
Operación 1: Intercambio de elementos 8 y 2, modifica el arreglo arr[] a {2, 50, 11, 8}.
Operación 2: el intercambio de elementos 8 y 50 modifica la array arr[] a {2, 8, 11, 50}.
La suma de la diferencia absoluta de los elementos adyacentes de la array modificada es 48, que es el mínimo.
Por lo tanto, el número mínimo de intercambios requeridos es 2.Entrada: arr[] = {3, 4, 2, 5, 1}
Salida: 2
Enfoque: El problema dado se puede resolver basándose en la observación de que la suma de la diferencia absoluta de los elementos adyacentes será mínima si la array se ordena en orden creciente o decreciente. Siga los pasos para resolver el problema.
- Encuentre el número mínimo de intercambios requeridos para clasificar la array dada en orden ascendente usando el enfoque que se describe en este artículo . Sea el conteo S1 .
- Encuentre el número mínimo de intercambios requeridos para ordenar la array dada en orden descendente usando el enfoque que se describe en este artículo . Sea el conteo S2 .
- Después de completar los pasos anteriores, imprima el mínimo del valor S1 y S2 como el número mínimo resultante de intercambios requeridos.
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; // Comparator to sort in the descending // order bool mycmp(pair<int, int> a, pair<int, int> b) { return a.first > b.first; } // Function to find the minimum number // of swaps required to sort the array // in increasing order int minSwapsAsc(vector<int> arr, int n) { // Stores the array elements with // its index pair<int, int> arrPos[n]; for (int i = 0; i < n; i++) { arrPos[i].first = arr[i]; arrPos[i].second = i; } // Sort the array in the // increasing order sort(arrPos, arrPos + n); // Keeps the track of // visited elements vector<bool> vis(n, false); // Stores the count of swaps required int ans = 0; // Traverse array elements for (int i = 0; i < n; i++) { // If the element is already // swapped or at correct position if (vis[i] || arrPos[i].second == i) continue; // Find out the number of // nodes in this cycle int cycle_size = 0; // Update the value of j int j = i; while (!vis[j]) { vis[j] = 1; // Move to the next element j = arrPos[j].second; // Increment cycle_size cycle_size++; } // Update the ans by adding // current cycle if (cycle_size > 0) { ans += (cycle_size - 1); } } return ans; } // Function to find the minimum number // of swaps required to sort the array // in decreasing order int minSwapsDes(vector<int> arr, int n) { // Stores the array elements with // its index pair<int, int> arrPos[n]; for (int i = 0; i < n; i++) { arrPos[i].first = arr[i]; arrPos[i].second = i; } // Sort the array in the // descending order sort(arrPos, arrPos + n, mycmp); // Keeps track of visited elements vector<bool> vis(n, false); // Stores the count of resultant // swap required int ans = 0; // Traverse array elements for (int i = 0; i < n; i++) { // If the element is already // swapped or at correct // position if (vis[i] || arrPos[i].second == i) continue; // Find out the number of // node in this cycle int cycle_size = 0; // Update the value of j int j = i; while (!vis[j]) { vis[j] = 1; // Move to the next element j = arrPos[j].second; // Increment the cycle_size cycle_size++; } // Update the ans by adding // current cycle size if (cycle_size > 0) { ans += (cycle_size - 1); } } return ans; } // Function to find minimum number of // swaps required to minimize the sum // of absolute difference of adjacent // elements int minimumSwaps(vector<int> arr) { // Sort in ascending order int S1 = minSwapsAsc(arr, arr.size()); // Sort in descending order int S2 = minSwapsDes(arr, arr.size()); // Return the minimum value return min(S1, S2); } // Drive Code int main() { vector<int> arr{ 3, 4, 2, 5, 1 }; cout << minimumSwaps(arr); return 0; }
Java
// Java program for the above approach import java.lang.*; import java.util.*; // Pair class class pair { int first, second; pair(int first, int second) { this.first = first; this.second = second; } } class GFG{ // Function to find the minimum number // of swaps required to sort the array // in increasing order static int minSwapsAsc(int[] arr, int n) { // Stores the array elements with // its index pair[] arrPos = new pair[n]; for(int i = 0; i < n; i++) { arrPos[i] = new pair(arr[i], i); } // Sort the array in the // increasing order Arrays.sort(arrPos, (a, b)-> a.first - b.first); // Keeps the track of // visited elements boolean[] vis= new boolean[n]; // Stores the count of swaps required int ans = 0; // Traverse array elements for(int i = 0; i < n; i++) { // If the element is already // swapped or at correct position if (vis[i] || arrPos[i].second == i) continue; // Find out the number of // nodes in this cycle int cycle_size = 0; // Update the value of j int j = i; while (!vis[j]) { vis[j] = true; // Move to the next element j = arrPos[j].second; // Increment cycle_size cycle_size++; } // Update the ans by adding // current cycle if (cycle_size > 0) { ans += (cycle_size - 1); } } return ans; } // Function to find the minimum number // of swaps required to sort the array // in decreasing order static int minSwapsDes(int[] arr, int n) { // Stores the array elements with // its index pair[] arrPos = new pair[n]; for(int i = 0; i < n; i++) { arrPos[i] = new pair(arr[i], i); } // Sort the array in the // descending order Arrays.sort(arrPos, (a, b)-> b.first - a.first); // Keeps track of visited elements boolean[] vis = new boolean[n]; // Stores the count of resultant // swap required int ans = 0; // Traverse array elements for(int i = 0; i < n; i++) { // If the element is already // swapped or at correct // position if (vis[i] || arrPos[i].second == i) continue; // Find out the number of // node in this cycle int cycle_size = 0; // Update the value of j int j = i; while (!vis[j]) { vis[j] = true; // Move to the next element j = arrPos[j].second; // Increment the cycle_size cycle_size++; } // Update the ans by adding // current cycle size if (cycle_size > 0) { ans += (cycle_size - 1); } } return ans; } // Function to find minimum number of // swaps required to minimize the sum // of absolute difference of adjacent // elements static int minimumSwaps(int[] arr) { // Sort in ascending order int S1 = minSwapsAsc(arr, arr.length); // Sort in descending order int S2 = minSwapsDes(arr, arr.length); // Return the minimum value return Math.min(S1, S2); } // Driver code public static void main(String[] args) { int[] arr = { 3, 4, 2, 5, 1 }; System.out.println(minimumSwaps(arr)); } } // This code is contributed by offbeat
Python3
# Python3 program for the above approach # Function to find the minimum number # of swaps required to sort the array # in increasing order def minSwapsAsc(arr, n): # Stores the array elements with # its index arrPos = [[arr[i], i] for i in range(n)] # Sort the array in the # increasing order arrPos = sorted(arrPos) # Keeps the track of # visited elements vis = [False] * (n) # Stores the count of swaps required ans = 0 # Traverse array elements for i in range(n): # If the element is already # swapped or at correct position if (vis[i] or arrPos[i][1] == i): continue # Find out the number of # nodes in this cycle cycle_size = 0 # Update the value of j j = i while (not vis[j]): vis[j] = 1 # Move to the next element j = arrPos[j][1] # Increment cycle_size cycle_size += 1 # Update the ans by adding # current cycle if (cycle_size > 0): ans += (cycle_size - 1) return ans # Function to find the minimum number # of swaps required to sort the array # in decreasing order def minSwapsDes(arr, n): # Stores the array elements with # its index arrPos = [[0, 0] for i in range(n)] for i in range(n): arrPos[i][0] = arr[i] arrPos[i][1] = i # Sort the array in the # descending order arrPos = sorted(arrPos)[::-1] # Keeps track of visited elements vis = [False] * n # Stores the count of resultant # swap required ans = 0 # Traverse array elements for i in range(n): # If the element is already # swapped or at correct # position if (vis[i] or arrPos[i][1] == i): continue # Find out the number of # node in this cycle cycle_size = 0 # Update the value of j j = i while (not vis[j]): vis[j] = 1 # Move to the next element j = arrPos[j][1] # Increment the cycle_size cycle_size += 1 # Update the ans by adding # current cycle size if (cycle_size > 0): ans += (cycle_size - 1) return ans # Function to find minimum number of # swaps required to minimize the sum # of absolute difference of adjacent # elements def minimumSwaps(arr): # Sort in ascending order S1 = minSwapsAsc(arr, len(arr)) # Sort in descending order S2 = minSwapsDes(arr, len(arr)) # Return the minimum value return min(S1, S2) # Drive Code if __name__ == '__main__': arr = [ 3, 4, 2, 5, 1 ] print (minimumSwaps(arr)) # This code is contributed by mohit kumar 29
Javascript
<script> // Javascript program for the above approach // Comparator to sort in the descending // order function mycmp(a, b) { return a[0] > b[0]; } // Function to find the minimum number // of swaps required to sort the array // in increasing order function minSwapsAsc(arr, n) { // Stores the array elements with // its index let arrPos = new Array(n); for (let i = 0; i < n; i++) arrPos[i] = new Array(2); for (let i = 0; i < n; i++) { arrPos[i][0] = arr[i]; arrPos[i][1] = i; } // Sort the array in the // increasing order arrPos.sort(function (a, b) { return a[0] - b[0] }) // Keeps the track of // visited elements let vis = new Array(n); for (let i = 0; i < n; i++) vis[i] = false // Stores the count of swaps required let ans = 0; // Traverse array elements for (let i = 0; i < n; i++) { // If the element is already // swapped or at correct position if (vis[i] || arrPos[i][1] == i) continue; // Find out the number of // nodes in this cycle let cycle_size = 0; // Update the value of j let j = i; while (!vis[j]) { vis[j] = 1; // Move to the next element j = arrPos[j][1]; // Increment cycle_size cycle_size++; } // Update the ans by adding // current cycle if (cycle_size > 0) { ans += (cycle_size - 1); } } return ans; } // Function to find the minimum number // of swaps required to sort the array // in decreasing order function minSwapsDes(arr, n) { // Stores the array elements with // its index let arrPos = new Array(n); for (let i = 0; i < n; i++) arrPos[i] = new Array(2); for (let i = 0; i < n; i++) { arrPos[i][0] = arr[i]; arrPos[i][1] = i; } // Sort the array in the // descending order arrPos.sort(function (a, b) { return b[0] - a[0] }) // Keeps track of visited elements let vis = new Array(n); for (let i = 0; i < n; i++) vis[i] = false // Stores the count of resultant // swap required let ans = 0; // Traverse array elements for (let i = 0; i < n; i++) { // If the element is already // swapped or at correct // position if (vis[i] || arrPos[i][1] == i) continue; // Find out the number of // node in this cycle let cycle_size = 0; // Update the value of j let j = i; while (!vis[j]) { vis[j] = 1; // Move to the next element j = arrPos[j][1]; // Increment the cycle_size cycle_size++; } // Update the ans by adding // current cycle size if (cycle_size > 0) { ans += (cycle_size - 1); } } return ans; } // Function to find minimum number of // swaps required to minimize the sum // of absolute difference of adjacent // elements function minimumSwaps(arr) { // Sort in ascending order let S1 = minSwapsAsc(arr, arr.length); // Sort in descending order let S2 = minSwapsDes(arr, arr.length); // Return the minimum value return Math.min(S1, S2); } // Drive Code let arr = [ 3, 4, 2, 5, 1 ]; document.write(minimumSwaps(arr)); // This code is contributed by Hritik </script>
2
Complejidad de tiempo: O(N * log N)
Espacio auxiliar: O(N)
Publicación traducida automáticamente
Artículo escrito por manupathria y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA