Array lexicográficamente más pequeña después de un máximo de K intercambios consecutivos

Dada una array arr[], encuentre la array lexicográficamente más pequeña que se puede obtener después de realizar un máximo de k intercambios consecutivos. 
Ejemplos: 
 

Input: arr[] = {7, 6, 9, 2, 1}
        k = 3
Output: arr[] = {2, 7, 6, 9, 1}
Explanation: Array is: 7, 6, 9, 2, 1
Swap 1:   7, 6, 2, 9, 1
Swap 2:   7, 2, 6, 9, 1
Swap 3:   2, 7, 6, 9, 1
So Our final array after k = 3 swaps : 
2, 7, 6, 9, 1

Input: arr[] = {7, 6, 9, 2, 1}
        k = 1
Output: arr[] = {6, 7, 9, 2, 1}
Le recomendamos encarecidamente que haga clic aquí y lo practique antes de pasar a la solución.

El enfoque ingenuo es generar toda la permutación de la array y elegir la más pequeña que satisfaga la condición de, como máximo, k intercambios. La complejidad de tiempo de este enfoque es Ω(n!), que definitivamente expirará para un gran valor de n.
Un enfoque eficiente es pensar con avidez. Primero elegimos el elemento más pequeño de la array a 1 , a 2 , a 3 … ( ak o a n ) [Consideramos a k cuando k es más pequeño, de lo contrario n]. Colocamos el elemento más pequeño a la a 0después de desplazar todos estos elementos 1 posición a la derecha. Restamos el número de intercambios (el número de intercambios es el número de turnos menos 1) de k. Si aún nos queda k > 0, aplicamos el mismo procedimiento desde la siguiente posición inicial, es decir, a 2 , a 3 ,…( ak o a n ) y luego lo colocamos en la posición a 1 . Así que seguimos aplicando el mismo proceso hasta que k se convierte en 0. 
 

C++

// C++ program to find lexicographically minimum
// value after k swaps.
#include<bits/stdc++.h>
using namespace std ;
 
// Modifies arr[0..n-1] to lexicographically smallest
// with k swaps.
void minimizeWithKSwaps(int arr[], int n, int k)
{
    for (int i = 0; i<n-1 && k>0; ++i)
    {
        // Set the position where we want
        // to put the smallest integer
        int pos = i;
        for (int j = i+1; j<n ; ++j)
        {
            // If we exceed the Max swaps
            // then terminate the loop
            if (j-i > k)
                break;
 
            // Find the minimum value from i+1 to
            // max k or n
            if (arr[j] < arr[pos])
                pos = j;
        }
 
        // Swap the elements from Minimum position
        // we found till now to the i index
        for (int j = pos; j>i; --j)
            swap(arr[j], arr[j-1]);
 
        // Set the final value after swapping pos-i
        // elements
        k -=  pos-i;
    }
}
 
// Driver code
int main()
{
    int arr[] = {7, 6, 9, 2, 1};
    int n = sizeof(arr)/sizeof(arr[0]);
    int k = 3;
 
    minimizeWithKSwaps(arr, n, k);
 
    //Print the final Array
    for (int i=0; i<n; ++i)
        cout << arr[i] <<" ";
}

Java

// Java program to find lexicographically minimum
// value after k swaps.
class GFG {
     
    // Modifies arr[0..n-1] to lexicographically
    // smallest with k swaps.
    static void minimizeWithKSwaps(int arr[], int n, int k)
    {
        for (int i = 0; i < n-1 && k > 0; ++i)
        {
             
            // Set the position where we want
            // to put the smallest integer
            int pos = i;
            for (int j = i+1; j < n ; ++j)
            {
                 
                // If we exceed the Max swaps
                // then terminate the loop
                if (j - i > k)
                    break;
     
                // Find the minimum value from i+1 to
                // max k or n
                if (arr[j] < arr[pos])
                    pos = j;
            }
     
            // Swap the elements from Minimum position
            // we found till now to the i index
            int temp;
             
            for (int j = pos; j>i; --j)
            {
                temp=arr[j];
                arr[j]=arr[j-1];
                arr[j-1]=temp;
            }
             
            // Set the final value after swapping pos-i
            // elements
            k -= pos-i;
        }
    }
     
    // Driver method
    public static void main(String[] args)
    {
         
        int arr[] = {7, 6, 9, 2, 1};
        int n = arr.length;
        int k = 3;
     
        minimizeWithKSwaps(arr, n, k);
     
        //Print the final Array
        for (int i=0; i<n; ++i)
            System.out.print(arr[i] +" ");
    }
}
 
// This code is contributed by Anant Agarwal.

Python3

# Python program to find lexicographically minimum
# value after k swaps.
def minimizeWithKSwaps(arr, n, k):
 
    for i in range(n-1):
 
        # Set the position where we want
    # to put the smallest integer
        pos = i
        for j in range(i+1, n):
 
            # If we exceed the Max swaps
        # then terminate the loop
            if (j-i > k):
                break
 
            # Find the minimum value from i+1 to
            # max (k or n)
            if (arr[j] < arr[pos]):
                pos = j
 
        # Swap the elements from Minimum position
        # we found till now to the i index
        for j in range(pos, i, -1):
            arr[j],arr[j-1] = arr[j-1], arr[j]
 
        # Set the final value after swapping pos-i
        # elements
        k -= pos - i
 
 
# Driver Code
n, k = 5, 3
arr = [7, 6, 9, 2, 1]
minimizeWithKSwaps(arr, n, k)
 
# Print the final Array
for i in range(n):
    print(arr[i], end = " ")

C#

// C# program to find lexicographically
// minimum value after k swaps.
using System;
 
class GFG {
     
    // Modifies arr[0..n-1] to lexicographically
    // smallest with k swaps.
    static void minimizeWithKSwaps(int []arr, int n,
                                              int k)
    {
        for (int i = 0; i < n-1 && k > 0; ++i)
        {
            // Set the position where we want
            // to put the smallest integer
            int pos = i;
            for (int j = i+1; j < n ; ++j)
            {
                // If we exceed the Max swaps
                // then terminate the loop
                if (j - i > k)
                    break;
     
                // Find the minimum value from
                // i + 1 to max k or n
                if (arr[j] < arr[pos])
                    pos = j;
            }
     
            // Swap the elements from Minimum position
            // we found till now to the i index
            int temp;
             
            for (int j = pos; j>i; --j)
            {
                temp=arr[j];
                arr[j]=arr[j-1];
                arr[j-1]=temp;
            }
             
            // Set the final value after
            // swapping pos-i elements
            k -= pos-i;
        }
    }
     
    // Driver method
    public static void Main()
    {
        int []arr = {7, 6, 9, 2, 1};
        int n = arr.Length;
        int k = 3;
         
        // Function calling
        minimizeWithKSwaps(arr, n, k);
     
        // Print the final Array
        for (int i=0; i<n; ++i)
          Console.Write(arr[i] +" ");
    }
}
 
// This code is contributed by nitin mittal.

php

<?php
// php program to find lexicographically minimum
// value after k swaps.
 
// Modifies arr[0..n-1] to lexicographically
// smallest with k swaps.
function minimizeWithKSwaps($arr, $n, $k)
{
    for ($i = 0; $i < $n-1 && $k > 0; ++$i)
    {
        // Set the position where we want
        // to put the smallest integer
        $pos = $i;
        for ($j = $i+1; $j < $n ; ++$j)
        {
            // If we exceed the Max swaps
            // then terminate the loop
            if ($j-$i > $k)
                break;
 
            // Find the minimum value from
            // i+1 to max k or n
            if ($arr[$j] < $arr[$pos])
                $pos = $j;
        }
 
        // Swap the elements from Minimum
        // position we found till now to
        // the i index
        for ($j = $pos; $j > $i; --$j)
        {
            $temp = $arr[$j];
            $arr[$j] = $arr[$j-1];
            $arr[$j-1] = $temp;
        }
         
        // Set the final value after
        // swapping pos-i elements
        $k -= $pos-$i;
    }
     
    //Print the final Array
    for ($i = 0; $i < $n; ++$i)
        echo $arr[$i] . " ";
}
 
// Driver code
$arr = array(7, 6, 9, 2, 1);
$n = count($arr);
$k = 3;
 
minimizeWithKSwaps($arr, $n, $k);
 
// This code is contributed by Sam007
?>

Javascript

<script>
    // Javascript program to find lexicographically
    // minimum value after k swaps.
     
    // Modifies arr[0..n-1] to lexicographically
    // smallest with k swaps.
    function minimizeWithKSwaps(arr, n, k)
    {
        for (let i = 0; i < n - 1 && k > 0; ++i)
        {
         
            // Set the position where we want
            // to put the smallest integer
            let pos = i;
            for (let j = i+1; j < n ; ++j)
            {
                // If we exceed the Max swaps
                // then terminate the loop
                if (j - i > k)
                    break;
       
                // Find the minimum value from
                // i + 1 to max k or n
                if (arr[j] < arr[pos])
                    pos = j;
            }
       
            // Swap the elements from Minimum position
            // we found till now to the i index
            let temp;
               
            for (let j = pos; j > i; --j)
            {
                temp = arr[j];
                arr[j] = arr[j - 1];
                arr[j - 1] = temp;
            }
               
            // Set the final value after
            // swapping pos-i elements
            k -= pos - i;
        }
    }
     
    let arr = [7, 6, 9, 2, 1];
    let n = arr.length;
    let k = 3;
 
    // Function calling
    minimizeWithKSwaps(arr, n, k);
 
    // Print the final Array
    document.write("Output: ");
    for (let i = 0; i < n; ++i)
      document.write(arr[i] + " ");
     
    // This code is contributed by divyesh072019.
</script>
Output: 2 7 6 9 1

Complejidad temporal: O(N 2
Espacio auxiliar: O(1)
Referencia:  
http://stackoverflow.com/questions/25539423/finding-minimal-lexicographical-array Shubham Bansal
contribuye con este artículo . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu artículo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks. Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.

 

Publicación traducida automáticamente

Artículo escrito por GeeksforGeeks-1 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 *