Dada una array arr[], encuentre la array lexicográficamente más grande que se puede obtener realizando como máximo k intercambios consecutivos.
Ejemplos:
Input : arr[] = {3, 5, 4, 1, 2}
k = 3
Output : 5, 4, 3, 2, 1
Explanation : Array given : 3 5 4 1 2
After swap 1 : 5 3 4 1 2
After swap 2 : 5 4 3 1 2
After swap 3 : 5 4 3 2 1
Input : arr[] = {3, 5, 1, 2, 1}
k = 3
Output : 5, 3, 2, 1, 1
Enfoque de fuerza bruta: genere todas las permutaciones de la array y luego elija la que satisfaga la condición de como máximo K intercambios. La complejidad temporal de este enfoque es O(n!) .
Enfoque optimizado: en este enfoque codicioso, primero encuentre el elemento más grande presente en la array que es mayor que (si el elemento de la primera posición no es el más grande) la primera posición y que se puede colocar en la primera posición con como máximo intercambios de K . Después de encontrar ese elemento, observe su índice. Luego, intercambie elementos de la array y actualice el valor K. Aplique este procedimiento para otras posiciones hasta que k no sea cero o la array se vuelva lexicográficamente más grande.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program to find lexicographically
// maximum value after k swaps.
#include <bits/stdc++.h>
using namespace std;
// Function which modifies the array
void KSwapMaximum(int arr[], int n, int k)
{
for (int i = 0; i < n - 1 && k > 0; ++i) {
// Here, indexPosition is set where we
// want to put the current largest integer
int indexPosition = i;
for (int j = i + 1; j < n; ++j) {
// If we exceed the Max swaps
// then break the loop
if (k <= j - i)
break;
// Find the maximum value from i+1 to
// max k or n which will replace
// arr[indexPosition]
if (arr[j] > arr[indexPosition])
indexPosition = j;
}
// Swap the elements from Maximum indexPosition
// we found till now to the ith index
for (int j = indexPosition; j > i; --j)
swap(arr[j], arr[j - 1]);
// Updates k after swapping indexPosition-i
// elements
k -= indexPosition - i;
}
}
// Driver code
int main()
{
int arr[] = { 3, 5, 4, 1, 2 };
int n = sizeof(arr) / sizeof(arr[0]);
int k = 3;
KSwapMaximum(arr, n, k);
// Print the final Array
for (int i = 0; i < n; ++i)
cout << arr[i] << " ";
}
Java
// Java program to find
// lexicographically
// maximum value after
// k swaps.
import java.io.*;
class GFG
{
static void SwapInts(int array[],
int position1,
int position2)
{
// Swaps elements
// in an array.
// Copy the first
// position's element
int temp = array[position1];
// Assign to the
// second element
array[position1] = array[position2];
// Assign to the
// first element
array[position2] = temp;
}
// Function which
// modifies the array
static void KSwapMaximum(int []arr,
int n, int k)
{
for (int i = 0;
i < n - 1 && k > 0; ++i)
{
// Here, indexPosition
// is set where we want to
// put the current largest
// integer
int indexPosition = i;
for (int j = i + 1; j < n; ++j)
{
// If we exceed the
// Max swaps then
// break the loop
if (k <= j - i)
break;
// Find the maximum value
// from i+1 to max k or n
// which will replace
// arr[indexPosition]
if (arr[j] > arr[indexPosition])
indexPosition = j;
}
// Swap the elements from
// Maximum indexPosition
// we found till now to
// the ith index
for (int j = indexPosition; j > i; --j)
SwapInts(arr, j, j - 1);
// Updates k after swapping
// indexPosition-i elements
k -= indexPosition - i;
}
}
// Driver code
public static void main(String args[])
{
int []arr = { 3, 5, 4, 1, 2 };
int n = arr.length;
int k = 3;
KSwapMaximum(arr, n, k);
// Print the final Array
for (int i = 0; i < n; ++i)
System.out.print(arr[i] + " ");
}
}
// This code is contributed by
// Manish Shaw(manishshaw1)
Python3
# Python program to find
# lexicographically
# maximum value after
# k swaps.
arr = [3, 5, 4, 1, 2]
# Function which
# modifies the array
def KSwapMaximum(n, k) :
global arr
for i in range(0, n - 1) :
if (k > 0) :
# Here, indexPosition
# is set where we want to
# put the current largest
# integer
indexPosition = i
for j in range(i + 1, n) :
# If we exceed the Max swaps
# then break the loop
if (k <= j - i) :
break
# Find the maximum value
# from i+1 to max k or n
# which will replace
# arr[indexPosition]
if (arr[j] > arr[indexPosition]) :
indexPosition = j
# Swap the elements from
# Maximum indexPosition
# we found till now to
# the ith index
for j in range(indexPosition, i, -1) :
t = arr[j]
arr[j] = arr[j - 1]
arr[j - 1] = t
# Updates k after swapping
# indexPosition-i elements
k = k - indexPosition - i
# Driver code
n = len(arr)
k = 3
KSwapMaximum(n, k)
# Print the final Array
for i in range(0, n) :
print ("{} " .
format(arr[i]),
end = "")
# This code is contributed by
# Manish Shaw(manishshaw1)
C#
// C# program to find
// lexicographically
// maximum value after
// k swaps.
using System;
class GFG
{
static void SwapInts(int[] array,
int position1,
int position2)
{
// Swaps elements in an array.
// Copy the first position's element
int temp = array[position1];
// Assign to the second element
array[position1] = array[position2];
// Assign to the first element
array[position2] = temp;
}
// Function which
// modifies the array
static void KSwapMaximum(int []arr,
int n, int k)
{
for (int i = 0;
i < n - 1 && k > 0; ++i)
{
// Here, indexPosition
// is set where we want to
// put the current largest
// integer
int indexPosition = i;
for (int j = i + 1; j < n; ++j)
{
// If we exceed the
// Max swaps then
// break the loop
if (k <= j - i)
break;
// Find the maximum value
// from i+1 to max k or n
// which will replace
// arr[indexPosition]
if (arr[j] > arr[indexPosition])
indexPosition = j;
}
// Swap the elements from
// Maximum indexPosition
// we found till now to
// the ith index
for (int j = indexPosition; j > i; --j)
SwapInts(arr, j, j - 1);
// Updates k after swapping
// indexPosition-i elements
k -= indexPosition - i;
}
}
// Driver code
static void Main()
{
int []arr = new int[]{ 3, 5, 4, 1, 2 };
int n = arr.Length;
int k = 3;
KSwapMaximum(arr, n, k);
// Print the final Array
for (int i = 0; i < n; ++i)
Console.Write(arr[i] + " ");
}
}
// This code is contributed by
// Manish Shaw(manishshaw1)
PHP
<?php
// PHP program to find
// lexicographically
// maximum value after
// k swaps.
function swap(&$x, &$y)
{
$x ^= $y ^= $x ^= $y;
}
// Function which
// modifies the array
function KSwapMaximum(&$arr, $n, $k)
{
for ($i = 0;
$i < $n - 1 &&
$k > 0; $i++)
{
// Here, indexPosition
// is set where we want to
// put the current largest
// integer
$indexPosition = $i;
for ($j = $i + 1;
$j < $n; $j++)
{
// If we exceed the Max swaps
// then break the loop
if ($k <= $j - $i)
break;
// Find the maximum value
// from i+1 to max k or n
// which will replace
// arr[indexPosition]
if ($arr[$j] > $arr[$indexPosition])
$indexPosition = $j;
}
// Swap the elements from
// Maximum indexPosition
// we found till now to
// the ith index
for ($j = $indexPosition;
$j > $i; $j--)
swap($arr[$j], $arr[$j - 1]);
// Updates k after swapping
// indexPosition-i elements
$k -= $indexPosition - $i;
}
}
// Driver code
$arr = array( 3, 5, 4, 1, 2 );
$n = count($arr);
$k = 3;
KSwapMaximum($arr, $n, $k);
// Print the final Array
for ($i = 0; $i < $n; $i++)
echo ($arr[$i]." ");
// This code is contributed by
// Manish Shaw(manishshaw1)
?>
Javascript
<script>
// JavaScript program to find
// lexicographically
// maximum value after
// k swaps.
function SwapLets(array, position1, position2)
{
// Swaps elements
// in an array.
// Copy the first
// position's element
let temp = array[position1];
// Assign to the
// second element
array[position1] = array[position2];
// Assign to the
// first element
array[position2] = temp;
}
// Function which
// modifies the array
function KSwapMaximum(arr, n, k)
{
for (let i = 0;
i < n - 1 && k > 0; ++i)
{
// Here, indexPosition
// is set where we want to
// put the current largest
// integer
let indexPosition = i;
for (let j = i + 1; j < n; ++j)
{
// If we exceed the
// Max swaps then
// break the loop
if (k <= j - i)
break;
// Find the maximum value
// from i+1 to max k or n
// which will replace
// arr[indexPosition]
if (arr[j] > arr[indexPosition])
indexPosition = j;
}
// Swap the elements from
// Maximum indexPosition
// we found till now to
// the ith index
for (let j = indexPosition; j > i; --j)
SwapLets(arr, j, j - 1);
// Updates k after swapping
// indexPosition-i elements
k -= indexPosition - i;
}
}
// Driver code
let arr = [ 3, 5, 4, 1, 2 ];
let n = arr.length;
let k = 3;
KSwapMaximum(arr, n, k);
// Print the final Array
for (let i = 0; i < n; ++i)
document.write(arr[i] + " ");
// This code is contributed by coode_hunt.
</script>
Producción:
5 4 3 1 2
Complejidad temporal: O(N*N)
Espacio auxiliar: O(1)
Publicación traducida automáticamente
Artículo escrito por Surya Priy y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA