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)