Intercambios mínimos adyacentes para mover el máximo y el mínimo a las esquinas

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. 
 

  1. Caso 1: Si l < r: Número de swaps = l + (nr-1)
  2. 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>
Producción: 

2

 

Complejidad de tiempo: O(N) 
 

Publicación traducida automáticamente

Artículo escrito por HGaur y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *