Dada una array de 2 * N enteros positivos donde cada elemento de la array se encuentra entre 1 y N y aparece exactamente dos veces en la array. La tarea es encontrar el número mínimo de intercambios adyacentes necesarios para organizar todos los elementos de array similares juntos.
Nota : no es necesario ordenar la array final (después de realizar intercambios).
Ejemplos:
Entrada: arr[] = { 1, 2, 3, 3, 1, 2 }
Salida: 5
Después del primer intercambio, la array será arr[] = { 1, 2, 3, 1, 3, 2 },
después de la segunda arr [] = { 1, 2, 1, 3, 3, 2 }, después del tercer arr[] = { 1, 1, 2, 3, 3, 2 },
después del cuarto arr[] = { 1, 1, 2, 3, 2, 3 }, después del quinto arr[] = { 1, 1, 2, 2, 3, 3 }
Entrada: arr[] = { 1, 2, 1, 2 }
Salida: 1
arr[2] puede ser intercambiado con arr[1] para obtener la posición requerida.
Enfoque : este problema se puede resolver utilizando un enfoque codicioso. Los siguientes son los pasos:
- Mantenga una array visited[] que indique que visited[curr_ele] es falso si la operación de intercambio no se ha realizado en curr_ele.
- Recorra la array original y si el elemento de la array actual aún no ha sido visitado, es decir , visited[arr[curr_ele]] = false , configúrelo como verdadero e itere sobre otro bucle desde la posición actual hasta el final de la array.
- Inicialice una cuenta variable que determinará la cantidad de intercambios necesarios para colocar al compañero del elemento actual en su posición correcta.
- En el ciclo anidado, incremente el conteo solo si el [curr_ele] visitado es falso (ya que si es verdadero, significa que curr_ele ya se colocó en su posición correcta).
- Si el compañero del elemento actual se encuentra en el ciclo anidado, sume el valor de conteo a la respuesta total.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ Program to find the minimum number of // adjacent swaps to arrange similar items together #include <bits/stdc++.h> using namespace std; // Function to find minimum swaps int findMinimumAdjacentSwaps(int arr[], int N) { // visited array to check if value is seen already bool visited[N + 1]; int minimumSwaps = 0; memset(visited, false, sizeof(visited)); for (int i = 0; i < 2 * N; i++) { // If the arr[i] is seen first time if (visited[arr[i]] == false) { visited[arr[i]] = true; // stores the number of swaps required to // find the correct position of current // element's partner int count = 0; for (int j = i + 1; j < 2 * N; j++) { // Increment count only if the current // element has not been visited yet (if is // visited, means it has already been placed // at its correct position) if (visited[arr[j]] == false) count++; // If current element's partner is found else if (arr[i] == arr[j]) minimumSwaps += count; } } } return minimumSwaps; } // Driver Code int main() { int arr[] = { 1, 2, 3, 3, 1, 2 }; int N = sizeof(arr) / sizeof(arr[0]); N /= 2; cout << findMinimumAdjacentSwaps(arr, N) << endl; return 0; }
Java
// Java Program to find the minimum number of // adjacent swaps to arrange similar items together import java.util.*; class solution { // Function to find minimum swaps static int findMinimumAdjacentSwaps(int arr[], int N) { // visited array to check if value is seen already boolean[] visited = new boolean[N + 1]; int minimumSwaps = 0; Arrays.fill(visited,false); for (int i = 0; i < 2 * N; i++) { // If the arr[i] is seen first time if (visited[arr[i]] == false) { visited[arr[i]] = true; // stores the number of swaps required to // find the correct position of current // element's partner int count = 0; for (int j = i + 1; j < 2 * N; j++) { // Increment count only if the current // element has not been visited yet (if is // visited, means it has already been placed // at its correct position) if (visited[arr[j]] == false) count++; // If current element's partner is found else if (arr[i] == arr[j]) minimumSwaps += count; } } } return minimumSwaps; } // Driver Code public static void main(String args[]) { int arr[] = { 1, 2, 3, 3, 1, 2 }; int N = arr.length; N /= 2; System.out.println(findMinimumAdjacentSwaps(arr, N)); } } // This code is contributed by // Sanjit_Prasad
Python3
# Python3 Program to find the minimum number of # adjacent swaps to arrange similar items together # Function to find minimum swaps def findMinimumAdjacentSwaps(arr, N) : # visited array to check if value is seen already visited = [False] * (N + 1) minimumSwaps = 0 for i in range(2 * N) : # If the arr[i] is seen first time if (visited[arr[i]] == False) : visited[arr[i]] = True # stores the number of swaps required to # find the correct position of current # element's partner count = 0 for j in range( i + 1, 2 * N) : # Increment count only if the current # element has not been visited yet (if is # visited, means it has already been placed # at its correct position) if (visited[arr[j]] == False) : count += 1 # If current element's partner is found elif (arr[i] == arr[j]) : minimumSwaps += count return minimumSwaps # Driver Code if __name__ == "__main__" : arr = [ 1, 2, 3, 3, 1, 2 ] N = len(arr) N //= 2 print(findMinimumAdjacentSwaps(arr, N)) # This code is contributed by Ryuga
C#
// C# Program to find the minimum // number of adjacent swaps to // arrange similar items together using System; class GFG { // Function to find minimum swaps static int findMinimumAdjacentSwaps(int []arr, int N) { // visited array to check // if value is seen already bool[] visited = new bool[N + 1]; int minimumSwaps = 0; for (int i = 0; i < 2 * N; i++) { // If the arr[i] is seen first time if (visited[arr[i]] == false) { visited[arr[i]] = true; // stores the number of swaps required to // find the correct position of current // element's partner int count = 0; for (int j = i + 1; j < 2 * N; j++) { // Increment count only if the current // element has not been visited yet (if is // visited, means it has already been placed // at its correct position) if (visited[arr[j]] == false) count++; // If current element's partner is found else if (arr[i] == arr[j]) minimumSwaps += count; } } } return minimumSwaps; } // Driver Code public static void Main(String []args) { int []arr = { 1, 2, 3, 3, 1, 2 }; int N = arr.Length; N /= 2; Console.WriteLine(findMinimumAdjacentSwaps(arr, N)); } } // This code is contributed by PrinciRaj1992
Javascript
<script> // Javascript Program to find the minimum number of // adjacent swaps to arrange similar items together // Function to find minimum swaps function findMinimumAdjacentSwaps(arr, N) { // visited array to check if value is seen already let visited = Array(N + 1).fill(false); let minimumSwaps = 0; for (let i = 0; i < 2 * N; i++) { // If the arr[i] is seen first time if (visited[arr[i]] == false) { visited[arr[i]] = true; // stores the number of swaps required to // find the correct position of current // element's partner let count = 0; for (let j = i + 1; j < 2 * N; j++) { // Increment count only if the current // element has not been visited yet (if is // visited, means it has already been placed // at its correct position) if (visited[arr[j]] == false) count++; // If current element's partner is found else if (arr[i] == arr[j]) minimumSwaps += count; } } } return minimumSwaps; } // driver code let arr = [ 1, 2, 3, 3, 1, 2 ]; let N = arr.length; N = Math.floor(N / 2); document.write(findMinimumAdjacentSwaps(arr, N)); </script>
5
Tiempo Complejidad: O(N 2 )
Espacio Auxiliar: O(N)
Publicación traducida automáticamente
Artículo escrito por Nishant Tanwar y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA