Dado un número N de elementos, encuentre el número mínimo de intercambios necesarios para que el elemento máximo esté al principio y el elemento mínimo al final con la condición de que solo se permita el intercambio de elementos adyacentes.
Ejemplos:
Entrada : a[] = {3, 1, 5, 3, 5, 5, 2}
Salida : 6
Paso 1: Intercambie 5 con 1 para hacer que la array sea {3, 5, 1, 3, 5, 5, 2 }
Paso 2: Intercambiar 5 con 3 para hacer el arreglo como {5, 3, 1, 3, 5, 5, 2}
Paso 3: Intercambiar 1 con 3 a su derecha para hacer el arreglo como {5, 3, 3, 1, 5, 5, 2}
Paso 4: Intercambiar 1 con 5 a su derecha para hacer la array como {5, 3, 3, 5, 1, 5, 2}
Paso 5: Intercambiar 1 con 5 a su derecha para hacer el arreglo como {5, 3, 3, 5, 5, 1, 2}
Paso 6: Intercambie 1 con 2 a su derecha para hacer el arreglo como {5, 3, 3, 5, 5, 2, 1}
Después de realizar 6 operaciones de intercambio 5 al principio y 1 al final
Entrada : a[] = {5, 6, 1, 3}
Salida : 2
El enfoque será encontrar el índice del elemento más grande (let l). Encuentre el índice del elemento más grande más a la izquierda si el elemento más grande aparece en la array más de una vez. De manera similar, encuentre el índice del elemento más pequeño más a la derecha (sea r). Existen dos casos para resolver este problema.
- Caso 1: Si l < r: Número de swaps = l + (nr-1)
- Caso 2: Si l > r: Número de intercambios = l + (nr-2), ya que se ha realizado un intercambio al intercambiar el elemento más grande al frente
C++
// CPP program to count Minimum number // of adjacent /swaps so that the largest element // is at beginning and the smallest element // is at last #include <bits/stdc++.h> using namespace std; // Function that returns the minimum swaps void solve(int a[], int n) { int maxx = -1, minn = a[0], l = 0, r = 0; for (int i = 0; i < n; i++) { // Index of leftmost largest element if (a[i] > maxx) { maxx = a[i]; l = i; } // Index of rightmost smallest element if (a[i] <= minn) { minn = a[i]; r = i; } } if (r < l) cout << l + (n - r - 2); else cout << l + (n - r - 1); } // Driver Code int main() { int a[] = { 5, 6, 1, 3 }; int n = sizeof(a)/sizeof(a[0]); solve(a, n); return 0; }
Java
// Java program to count Minimum number // of swaps so that the largest element // is at beginning and the // smallest element is at last import java.io.*; class GFG { // Function performing calculations public static void minimumSwaps(int a[], int n) { int maxx = -1, minn = a[0], l = 0, r = 0; for (int i = 0; i < n; i++) { // Index of leftmost largest element if (a[i] > maxx) { maxx = a[i]; l = i; } // Index of rightmost smallest element if (a[i] <= minn) { minn = a[i]; r = i; } } if (r < l) System.out.println(l + (n - r - 2)); else System.out.println(l + (n - r - 1)); } // Driver Code public static void main(String args[]) throws IOException { int a[] = { 5, 6, 1, 3 }; int n = a.length; minimumSwaps(a, n); } }
Python3
# Python3 program to count # Minimum number of adjacent # swaps so that the largest # element is at beginning and # the smallest element is at last. def minSwaps(arr): '''Function that returns the minimum swaps''' n = len(arr) maxx, minn, l, r = -1, arr[0], 0, 0 for i in range(n): # Index of leftmost # largest element if arr[i] > maxx: maxx = arr[i] l = i # Index of rightmost # smallest element if arr[i] <= minn: minn = arr[i] r = i if r < l: print(l + (n - r - 2)) else: print(l + (n - r - 1)) # Driver code arr = [5, 6, 1, 3] minSwaps(arr) # This code is contributed # by Tuhin Patra
C#
// C# program to count Minimum // number of swaps so that the // largest element is at beginning // and the smallest element is at last using System; class GFG { // Function performing calculations public static void minimumSwaps(int []a, int n) { int maxx = -1, l = 0, minn = a[0], r = 0; for (int i = 0; i < n; i++) { // Index of leftmost // largest element if (a[i] > maxx) { maxx = a[i]; l = i; } // Index of rightmost // smallest element if (a[i] <= minn) { minn = a[i]; r = i; } } if (r < l) Console.WriteLine(l + (n - r - 2)); else Console.WriteLine(l + (n - r - 1)); } // Driver Code public static void Main() { int []a = { 5, 6, 1, 3 }; int n = a.Length; // Calling function minimumSwaps(a, n); } } // This code is contributed by anuj_67.
PHP
<?php // PHP program to count Minimum // number of adjacent /swaps so // that the largest element is // at beginning and the smallest // element is at last // Function that returns // the minimum swaps function solve($a, $n) { $maxx = -1; $minn = $a[0]; $l = 0; $r = 0; for ($i = 0; $i < $n; $i++) { // Index of leftmost // largest element if ($a[$i] > $maxx) { $maxx = $a[$i]; $l = $i; } // Index of rightmost // smallest element if ($a[$i] <= $minn) { $minn = $a[$i]; $r = $i; } } if ($r < $l) echo $l + ($n - $r - 2); else echo $l + ($n - $r - 1); } // Driver Code $a = array(5, 6, 1, 3); $n = count($a); solve($a, $n); // This code is contributed // by anuj_67. ?>
Javascript
<script> // JavaScript program to count Minimum number // of adjacent /swaps so that the largest element // is at beginning and the smallest element // is at last // Function that returns the minimum swaps function solve(a, n) { let maxx = -1, minn = a[0], l = 0, r = 0; for (let i = 0; i < n; i++) { // Index of leftmost largest element if (a[i] > maxx) { maxx = a[i]; l = i; } // Index of rightmost smallest element if (a[i] <= minn) { minn = a[i]; r = i; } } if (r < l) document.write(l + (n - r - 2)); else document.write( l + (n - r - 1)); } // Driver Code let a = [ 5, 6, 1, 3 ]; let n = a.length; solve(a, n); </script>
2
Complejidad de tiempo: O(N)