¿Cuál es la mejor manera de realizar operaciones de intercambio K en un entero de N dígitos para obtener el máximo número posible?

ALGORITMO:

1. A partir del primer dígito, verifique los siguientes K dígitos. Registre la posición del más grande. Aquí K = Operación de intercambio.
2. Burbujea el dígito más grande a la cima. Reducir K por no. de permutas. Restablezca K a K = K- (distancia del dígito más grande desde la parte superior).
3. Mover al segundo dígito, repetir # 1 con el nuevo valor de K.
4. Repita 3 hasta K> 0 o no. de dígitos están agotados.

CÓDIGO:

  #include 
 usando el espacio de nombres estándar;
 int arr [100005], n;
 int findMaxIndex (int * arr, int start, int end)
 {
	 int max_index = inicio;
	 for (int curr = start; curr <= min (n-1, end); curr ++)
	 {
	 if (arr [curr]> arr [max_index])
	 {
		 max_index = curr;
	 }
 }
	 return max_index;
 }
 vacío printArray (int * arr, int length)
 {
	 para (int i = 0; i  :: max () ;;
	 para (int j = 0; (j  0); ++ j)
	 {
		 max_index = findMaxIndex (arr, j, j + swaps);
		 if (j! = max_index)
		 {
			 for (int i = max_index; i> j; i -) {
				 int temp = arr [i];
				 arr [i] = arr [i-1];
				 arr [i-1] = temp;
			 }
		 }	
		 swaps = swaps - (abs (max_index - j));
	 }
 }
 int main ()
 {
	 int t, k;
	 cin >> n >> k;  // n-Longitud del número // k-Número de operaciones de intercambio
	 cuerda s;  // Entrada de número como cadena
	 cin >> s;
	 para (int i = 0; i 

Aquí está la solución.

  paquete com.algorithm;

 import java.util.ArrayList;
 import java.util.Arrays;
 import java.util.Collections;
 import java.util.Comparator;
 import java.util.List;

 clase pública SwapToMax {

	 public static void main (String [] args) {
		 System.out.println (swap ("876959", 3));
	 }

	 intercambio estático privado de cadenas (valor de cadena, int k) {
		 return swapToMax (Arrays.asList (valor), k, 0);
	 }

	 Private static String swapToMax (Lista de valores , int k, int level) {
		 si (k == 0) {
			 return Collections.max (valores, nuevo comparador  () {

				 @Anular
				 public int compare (Cadena o1, Cadena o2) {
					 int i = Integer.parseInt (o1);
					 int j = Integer.parseInt (o2);
					 devuelve Integer.compare (i, j);
				 }
			 });
		 } más {
			 Lista  newValues ​​= new ArrayList <> ();

			 para (Cadena de cadena: valores) {
				 List  maxLocations = maxLocations (cadena, nivel);
				 for (entero entero: maxLocations) {
					 newValues.add (swap (cadena, entero, nivel));
				 }
			 }

			 return swapToMax (nuevosValores, k - 1, nivel + 1);

		 }
	 }

	 intercambio de cadenas estático privado (cadena de cadenas, número entero entero, nivel int) {
		 StringBuilder sb = new StringBuilder (cadena);
		 temp temp = sb.charAt (entero);
		 sb.setCharAt (entero, string.charAt (nivel));
		 sb.setCharAt (nivel, temp);
		 return sb.toString ();
	 }

	 Lista estática privada  maxLocations (String string, int start) {
		 char [] array = string.toCharArray ();

		 List  maxLocations = new ArrayList <> ();
		 maxLocations.add (inicio);

		 char max = array [inicio];

		 for (int i = start + 1; i  max) {
				 maxLocations.clear ();
				 maxLocations.add (i);
				 max = matriz [i];
			 }
		 }

		 return maxLocations;
	 }

 }

Para cada dígito, podemos encontrar el elemento más grande que está a la derecha y asegurarnos de que si hay múltiples ocurrencias del mismo número, lo intercambiemos con la ocurrencia más a la derecha.
Por ejemplo, en el caso de 7899 y K = 1, 7 puede intercambiarse con 9 en la posición 4, -> 9897
ahora si K = 2, 8 puede intercambiarse con 9 en pos 3 -> 9987

El tiempo comlpexity => Para K swaps, el caso promedio es O (N x K)
pero el peor de los casos puede ser O (N ^ 2), porque si el número es el más alto posible, podemos seguir buscando el dígito para intercambiar hasta el último que conduzca a N ^ 2.

tipo de selección

no funciona para 8799 con k = 2