tiene sumar suma saber pseint para número numeros numero los entero dígitos digitos determinar descomponer dado cuantos como algoritmo algorithm

algorithm - sumar - Algoritmo para encontrar el entero más pequeño intercambiando un par de dígitos en un entero dado



como saber si un numero es entero en pseint (7)

Dado un entero positivo ( en forma de una matriz de dígitos ). Se nos permite intercambiar un par de dígitos en el número dado. Necesitamos devolver el entero más pequeño posible que se pueda obtener. Tenga en cuenta que debe ser un número entero válido, es decir, no debe contener 0 iniciales.

Por ejemplo:-

  1. 93561 devuelve 13569
  2. 596 devoluciones 569
  3. 10234 devuelve 10234
  4. 120 devoluciones 102
  5. 10091 devuelve 10019
  6. 98761111 devuelve 18761119

¿Hay un algoritmo O(n) para este problema? He pensado en algunas maneras para esto:

  1. Encuentra el min. dígito ( minDIgit ) en el entero dado (excepto 0) y cámbielo con el MSB, si MSB != minDigit . Si MSB==minDigit , entonces encuentra el siguiente min. Dígalo y cámbielo por el más significativo, pero 1 dígito y así sucesivamente. Esto podría ser O(n^2) en el peor de los casos.
  2. Cree una array/vector de std::pair de dígitos e índice y ordénelos en orden creciente (de acuerdo con los valores de dígitos; primero mantenga los índices más bajos para los valores de dígitos coincidentes). Iterar a través de la matriz ordenada. Intercambia el MSB con el primer dígito. Si el dígito mínimo tiene un índice correspondiente como MSB, intercambie el MSB pero 1 lugar con el siguiente dígito mínimo. Si el siguiente dígito mínimo tiene el índice correspondiente de MSB pero 1 lugar, entonces intercambie el MSB pero el lugar 2 con este próximo minuto. dígito y así sucesivamente. Esto debería ser O(nlog(n)) .

Alguien puede sugerir un mejor algoritmo.

ACTUALIZACIÓN 1: Después de pensar un poco, el segundo algo que propuse funcionaría perfectamente bien (probablemente, excepto en algunos casos de esquina, que pueden manejarse por separado). Además, puedo ordenar el par (dígito, índice) utilizando el ordenamiento de conteo (según los valores de los dígitos), que es un ordenamiento estable en tiempo O(n) . ¿Hay algún defecto en mi argumento?

ACTUALIZACIÓN 2: Mi segundo algo funcionaría (aunque con más controles para casos de esquina y 0) y eso también en tiempo O(n) con orden de counting sort . Pero la solución dada por @GaborSch es mucho más simple, así que no me molestaré en dar un código adecuado para mis algoritmos.

Aquí está el código Java para el problema anterior que satisface todos los casos de prueba mencionados.

public static String smallestNumber(String num) { int length = num.length(); char[] c = num.toCharArray(); Map<Character, Integer> map = new HashMap<>(); for (int i = 0; i < length; i++) { map.put(c[i], i); } int count = 0; boolean flag = true; int ind = -1; for (int i = 0; i < length; i++) { int min = c[i]; for (int j = i + 1; j < length; j++) { if (flag) { if (min > c[j] && c[j] != ''0'') { min = c[j]; ind = j; } } else { if (min > c[j]) { min = c[j]; ind = j; } } } if (ind != -1) { char temp = c[i]; int index = map.get(c[ind]); c[i] = c[ind]; c[index] = temp; count++; } flag = false; if (count == 1) break; } return String.valueOf(c); }

Aquí hay un simple algoritmo O(n) :

- Record ''false'' for each of ten digit values, 0 through 9 - Work through the number''s digits, left-to-right - If the digit value is associated with ''true'' go to the next digit and continue - Record ''true'' for this digit - Search all the digits to the right for the right-most, smallest digit (except zero for the first digit in the number) and swap if the lowest digit found (if any) is less than the current digit - If swapped, report success and stop - If not swapped, go to the next digit and continue - If we reach the end of the digit list, report a lack of success and stop

Esto puede parecer que no es O (n) en la primera inspección, sin embargo, después de darse cuenta de que el bucle interno no puede ejecutarse más de diez veces, se hace evidente que es O(n) desde O(n - 10 + 10*n) = O(11*n - 10) = O(n) .

Como preparación, recorramos los dígitos y marcamos las últimas posiciones de los dígitos en una matriz [10] (llámelo en last ) (incluidos 0 s). Eso es O (n).

A continuación, comenzamos a iterar a través de dígitos de izquierda a derecha. Para cada posición, intentamos encontrar el dígito más pequeño cuya última posición es mayor que nuestra posición actual (restricción de posición). También ese dígito debe ser más pequeño que el dígito actual.

Si estamos en la primera posición, comenzamos el last bucle desde 1 (de lo contrario, desde 0 ), hasta el valor del dígito actual (no incluido).

Si encontramos dicho dígito (en relación con la restricción de posición), cambiamos (y rompemos el bucle). Si no lo hacemos, pasamos al siguiente dígito. El costo es como máximo O (n * 9), que es O (n).

El costo total es O (n) + O (n) * O (9) = O (n).

¿Cómo funciona el algoritmo en los ejemplos?

93561 -> it can swap in the first cycle 596 -> skipping the first cycle, then finds ''6'' because of the position constraint (comparing position ''1'' with last[5] = 0, last[6] = 2) 10234 -> does not find anything because of the position constraint 93218910471211292416 -> finds the last occurrence of ''1'' to replace ''9'' 98761111 -> it can swap in the first cycle (last[1] = 7, so it will change the last occurrence) 555555555555555555596 -> iterates until the ''9'', then you skip last[5] but finds last[6] as a good swap 120 -> at pos 0 (1) cannot find a non-zero element less than 1, so skip at pos 1 (2) can find 0 on position 2, so we swap

Una vez más, aquí hacemos una iteración en los dígitos (para realizar un análisis previo de los datos), y luego una iteración para encontrar el MSB. En la segunda iteración, iteramos en la last , que es de tamaño constante (a lo sumo 9).

Puede optimizar aún más el algoritmo agregando un seguimiento del valor mínimo cuando vale la pena comenzar el ciclo en last , pero eso ya es una optimización. La versión anterior contenía eso, verifique el historial si está interesado :)

Me gustaría iterar sobre la matriz comenzando en el extremo derecho. Almacene el dígito a la derecha como el dígito más pequeño y el dígito máximo y comience a moverse a la izquierda, si alcanza un nuevo número más pequeño, llámelo potencial más pequeño. Si sigue moviéndose hacia la izquierda y encuentra un número menor, haga que el menor sea el potencial. Si encuentra un número mayor, reduzca el potencial al menor y intente almacenar el mayor como máximo dígito. Cada vez que golpee un dígito más grande que el más pequeño, conviértalo en el nuevo dígito máximo. Si llegas al final, intercambia el dígito máximo y el dígito más pequeño. En python (esto funciona y es O (n))

def swap_max(digits): i = len(digits) - 1 while i > 0: if digits[i] == 0: i-= 1 else: break max_i = i min_i = i pot_i = i z_i = -1 nz_i = i i = len(digits) - 1 while i >= 0: if digits[i] > digits[pot_i]: max_i = i min_i = pot_i if digits[i] < digits[min_i] and digits[i] != 0: pot_i = i if digits[i] == 0 and z_i == -1: z_i = i if digits[i] != 0 and i > 0: nz_i = i i -= 1 if z_i != -1 and max_i != 0 and max_i < z_i: min_i = z_i i = nz_i max_i = i elif max_i == min_i and z_i != -1: i = nz_i if i < z_i: min_i = z_i max_i = i v = digits[min_i] digits[min_i] = digits[max_i] digits[max_i] = v return digits #TESTING THE FUNCTION tests = [93561,596,10234,120,10091,98761111,1001,1010,1103,120,93218910471211292416] results = [13569,569,10234,102,10019,18761119,1001,1001,1013,102,13218910471211292496] tests = map(list,map(str,tests)) results = map(list,map(str,results)) for i in range(len(tests)): res ="".join(map(str,swap_max(map(int,tests[i])))) print res,"".join(results[i]) if res=="".join(results[i]): print "PASSED/n" else: print "FAILED/n"

Esto terminó trabajando para todos los ejemplos. También tiene la ventaja de ser el uso de memoria O (1).

Primero cuente cada dígito, guárdelo en una matriz ( counts[10] ).

Desde la izquierda, compruebe los dígitos (a continuación se muestra la descripción del bucle):

Compruebe que hay un dígito en los counts que es más pequeño que él. Elige el más pequeño. Excepción: 0 no está permitido para el primer dígito.

  • Si hay uno, swap, está listo (¡salga del bucle!).
  • De lo contrario, disminuya el dígito en counts , y vaya al siguiente dígito.

Por cada dígito que haces, O (1) trabaja. Entonces todo el algo es O (n).

Para intercambiar desea utilizar los dígitos menos significativos (más a la derecha). Puede almacenar estas ubicaciones en la búsqueda inicial, o justo antes de intercambiar puede buscar el primer dígito coincidente desde el final.

Variación leve del algoritmo de Karoly Horvath

Puede ordenar por radix la matriz de dígitos en O (n).

Ahora tenemos 2 listas: ordenadas y reales. Actual es nuestra matriz original.

Iterar sobre real de izquierda a derecha,

para cada valor, extraiga los elementos de Ordenados hasta que alcancemos un valor cuya posición en la matriz original sea <posición de real [i]

Si el valor de la cabecera de la lista ordenada es <actual [i], intercambiamos y terminamos. de lo contrario continuar

La clasificación se realizó en tiempo O (n). A lo sumo, sacamos n elementos del total de la lista ordenada, e iteramos sobre la lista original solo una vez, por lo que todo el algoritmo debe ser O (n) en el tiempo y el espacio.

Por supuesto, hay algunos casos especiales que comprueban un intercambio de 0 con el elemento más a la izquierda, pero eso no afecta la complejidad.

PseudoCódigo: O (n)

1) Divida el número en dígitos individuales, diga dígito [10] (como se dijo en otra respuesta). Init incPos = -1 .

2) Recorra desde el dígito más a la derecha, para encontrar los incPos más crecientes a la izquierda ( incPos ). es decir, mientras se atraviesa, compare el elemento k + 1 con el elemento kth . Para, cada dígito [k] ≠ 0, si digit[k] >= digit[k+1] , marque incPos como k . Recorra hasta la izquierda más y encuentre los menos incPos.

4) Si incPos == -1 devuelve num, si no, pase de incPos a n para encontrar el dígito de Right-Most-Minimum (como se describe en BLOQUEO a continuación), intercambie con el dígito de Mínimo de derecho y devuelva. (seguramente habrá al menos 1 dígito).

E.g 93561 -> IncPos = 0, Right most minimum : 1 at pos 4 596 -> IncPos = 1, Right most minimum : 6 at pos 2 10234 -> IncPos = -1, return 10234 93218910471211292416 -> IncPos = 0, Right most minimum : 1 at pos 18 98761111 -> IncPos = 0, Right most minimum : 1 at pos 7

5) Formar el número con nuevos dígitos. Número de devolución.