Dada una array arr[] de enteros distintos de 1 a N. La tarea es encontrar el número mínimo de intercambios necesarios para ordenar la array.
Ejemplo:
Input: arr[] = { 7, 1, 3, 2, 4, 5, 6 } Output: 5 Explanation: i arr swap (indices) 0 [7, 1, 3, 2, 4, 5, 6] swap (0, 3) 1 [2, 1, 3, 7, 4, 5, 6] swap (0, 1) 2 [1, 2, 3, 7, 4, 5, 6] swap (3, 4) 3 [1, 2, 3, 4, 7, 5, 6] swap (4, 5) 4 [1, 2, 3, 4, 5, 7, 6] swap (5, 6) 5 [1, 2, 3, 4, 5, 6, 7] Therefore, total number of swaps = 5 Input: arr[] = { 2, 3, 4, 1, 5 } Output: 3
Acercarse:
- Para cada índice en arr[] .
- Compruebe si el elemento actual está en su posición correcta o no. Dado que la array contiene elementos distintos del 1 al N, podemos simplemente comparar el elemento con su índice en la array para verificar si está en la posición correcta.
- Si el elemento actual no está en su posición correcta, intercambie el elemento con el elemento que ha ocupado su lugar.
- De lo contrario, verifique el siguiente índice.
A continuación se muestra la implementación del enfoque anterior:
C++
#include <iostream> using namespace std; // Function to find minimum swaps int minimumSwaps(int arr[],int n) { // Initialise count variable int count = 0; int i = 0; while (i < n) { // If current element is // not at the right position if (arr[i] != i + 1) { while (arr[i] != i + 1) { int temp = 0; // Swap current element // with correct position // of that element temp = arr[arr[i] - 1]; arr[arr[i] - 1] = arr[i]; arr[i] = temp; count++; } } // Increment for next index // when current element is at // correct position i++; } return count; } // Driver code int main() { int arr[] = { 2, 3, 4, 1, 5 }; int n = sizeof(arr)/sizeof(arr[0]); // Function to find minimum swaps cout << minimumSwaps(arr,n) ; } // This code is contributed by AnkitRai01
Java
// Java program to find the minimum // number of swaps required to sort // the given array import java.io.*; import java.util.*; class GfG { // Function to find minimum swaps static int minimumSwaps(int[] arr) { // Initialise count variable int count = 0; int i = 0; while (i < arr.length) { // If current element is // not at the right position if (arr[i] != i + 1) { while (arr[i] != i + 1) { int temp = 0; // Swap current element // with correct position // of that element temp = arr[arr[i] - 1]; arr[arr[i] - 1] = arr[i]; arr[i] = temp; count++; } } // Increment for next index // when current element is at // correct position i++; } return count; } // Driver code public static void main(String[] args) { int arr[] = { 2, 3, 4, 1, 5 }; // Function to find minimum swaps System.out.println(minimumSwaps(arr)); } }
Python3
# Python3 program to find the minimum # number of swaps required to sort # the given array # Function to find minimum swaps def minimumSwaps(arr): # Initialise count variable count = 0; i = 0; while (i < len(arr)): # If current element is # not at the right position if (arr[i] != i + 1): while (arr[i] != i + 1): temp = 0; # Swap current element # with correct position # of that element temp = arr[arr[i] - 1]; arr[arr[i] - 1] = arr[i]; arr[i] = temp; count += 1; # Increment for next index # when current element is at # correct position i += 1; return count; # Driver code if __name__ == '__main__': arr = [ 2, 3, 4, 1, 5 ]; # Function to find minimum swaps print(minimumSwaps(arr)); # This code is contributed by 29AjayKumar
C#
// C# program to find the minimum // number of swaps required to sort // the given array using System; class GfG { // Function to find minimum swaps static int minimumSwaps(int[] arr) { // Initialise count variable int count = 0; int i = 0; while (i < arr.Length) { // If current element is // not at the right position if (arr[i] != i + 1) { while (arr[i] != i + 1) { int temp = 0; // Swap current element // with correct position // of that element temp = arr[arr[i] - 1]; arr[arr[i] - 1] = arr[i]; arr[i] = temp; count++; } } // Increment for next index // when current element is at // correct position i++; } return count; } // Driver code public static void Main(String[] args) { int []arr = { 2, 3, 4, 1, 5 }; // Function to find minimum swaps Console.WriteLine(minimumSwaps(arr)); } } // This code is contributed by 29AjayKumar
Javascript
<script> // javascript program to find the minimum // number of swaps required to sort // the given array // Function to find minimum swaps function minimumSwaps(arr) { // Initialise count variable let count = 0; let i = 0; while (i < arr.length) { // If current element is // not at the right position if (arr[i] != i + 1) { while (arr[i] != i + 1) { let temp = 0; // Swap current element // with correct position // of that element temp = arr[arr[i] - 1]; arr[arr[i] - 1] = arr[i]; arr[i] = temp; count++; } } // Increment for next index // when current element is at // correct position i++; } return count; } // Driver code let arr = [2, 3, 4, 1, 5 ]; // Function to find minimum swaps document.write(minimumSwaps(arr)); </script>
Producción:
3
Complejidad de tiempo : O (N) donde N es el tamaño de la array.
Espacio Auxiliar: O(1)
Publicación traducida automáticamente
Artículo escrito por riteshroshan7 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA