Cómo formar el número más pequeño posible a partir de un número dado en JavaScript

En este tutorial, implementaremos un algoritmo para formar el número más pequeño posible con ES6.

Input: 55010 7652634
Output: 10055 2345667

Nota : El número transformado no debe comenzar con 0 si tiene al menos un carácter distinto de cero.

Usaremos dos enfoques diferentes para resolver este problema. Todo estará escrito en ES6.

  • En el primer enfoque, asumiremos que el número proporcionado está en formato de cadena y lo resolveremos usando una clasificación que tomará O (nlogn).
  • En el segundo enfoque, resolveremos con valor numérico con O (d) tiempo, donde d es el número de dígitos.

Usando la clasificación O (nlogn).

Implementación

  • Convertiremos el número a la matriz de caracteres y luego ordenaremos esa matriz.
  • Después de ordenar, comprobaremos si el primer carácter de la matriz es 0.
  • Si no es 0, uniremos la matriz y la devolveremos.
  • Si es 0, encontraremos el primer número distinto de cero, lo intercambiaremos con 0 y lo devolveremos.
function smallestPossibleNumber(num){
//Create a character array and sort it in ascending orderlet sorted = num.split('').sort();
//Check if first character is not 0 then join and return it if(sorted[0] != '0'){ return sorted.join('');}
//find the index of the first non - zero character let index = 0; for(let i = 0; i  "0"){ index = i; break; } }
//Swap the indexes let temp = sorted[0]; sorted[0] = sorted[index]; sorted[index] = temp;
//return the string after joining the characters of array return sorted.join(''); }

Ejecutando el programa

Input:console.log(smallestPossibleNumber('55010'));console.log(smallestPossibleNumber('7652634'));console.log(smallestPossibleNumber('000001'));console.log(smallestPossibleNumber('000000'));
Output:100552345667100000000000
/*How it works let sorted = num.split('').sort(); = ['5','5','0','1','0'].sort() = ['0','0','1','5','5'] if(sorted[0] != '0'){ // '0' != '0' condition fails return sorted.join(''); } //Find the index of the first non - zero character let index = 0; for(let i = 0; i  '0'){ // '1' > '0' index = i; // index = 2; break; // break; } } //swap the index var temp = sorted[0]; sorted[0] = sorted[index]; sorted[index] = temp; //return the string return sorted.join('');*/

Cómo funciona

Primero creamos la matriz de caracteres como ['5', '5', '0', '1', 0]. Luego ordenamos esto a ['0', '0', '1', '5', '5']Después de esto, encontramos el primer elemento distinto de cero y lo intercambiamos con los primeros elementos cero como ['1', '0', '0', '5', '5']. Ahora que tenemos nuestro número más pequeño listo, solo necesitamos concatenarlos y devolverlo.

Obtenga más información sobre dividir (), ordenar (), unirse ().

Complejidad del tiempo: O (nlogn).

Complejidad espacial: O (n).

Explicación de la complejidad del tiempo y el espacio

Estamos creando una matriz de caracteres que llevará O (n) tiempo. Luego, ordenar la matriz tomará O (nlogn).

Después de eso, estamos encontrando el índice del número más pequeño distinto de cero que puede tomar O (n) en el peor de los casos y unirse a la matriz para crear la cadena tomará O (n). Como estas todas las operaciones se están ejecutando una tras otra. Entonces, la complejidad del tiempo es O (n + nlogn + n + n) = O (nlogn).

Estamos creando una matriz de caracteres a partir de la cadena, por lo que la complejidad del espacio es O (n).

Usando valor numérico O (logn).

Hay un inconveniente en este enfoque: si el número solo contiene ceros, devolverá un solo cero.

Implementación

  • Crearemos una matriz de números del 0 al 9.
  • Luego, realizaremos un seguimiento de los dígitos presentes en el número aumentando su recuento en la matriz.
  • Después de eso, encontraremos el dígito más pequeño distinto de cero y disminuiremos su recuento en 1.
  • Al final, recrearemos el número organizándolos en orden ascendente y devolveremos el resultado.
  • Esta solución se basa en el tipo de conteo.
function smallestPossibleNumber(num) { // initialize frequency of each digit to Zero let freq = [0, 0, 0, 0, 0, 0, 0, 0, 0, 0]; // count frequency of each digit in the number while (num > 0){ let d = parseInt(num % 10); // extract last digit freq[d]++; // increment counting num = parseInt(num / 10); //remove last digit }
// Set the LEFTMOST digit to minimum expect 0 let result = 0; for (let i = 1 ; i <= 9 ; i++) { if (freq[i] != 0) { result = i; freq[i]--; break; } } // arrange all remaining digits // in ascending order for (let i = 0 ; i <= 9 ; i++) { while (freq[i]-- != 0){ result = result * 10 + i; } } return result; }

Ejecutando el programa

Input:console.log(smallestPossibleNumber('55010'));console.log(smallestPossibleNumber('7652634'));console.log(smallestPossibleNumber('000001'));console.log(smallestPossibleNumber('000000'));
Output:10055234566710
/* How it works // initialize frequency of each digit to Zero let freq = [0, 0, 0, 0, 0, 0, 0, 0, 0, 0]; // count frequency of each digit in the number while (num > 0){ let d = parseInt(num % 10); // extract last digit freq[d]++; // increment counting num = parseInt(num / 10); //remove last digit } //After incrementing count //freq = [2, 1, 0, 0, 0, 2, 0, 0, 0, 0] // Set the LEFTMOST digit to minimum expect 0 let result = 0; for (let i = 1 ; i <= 9 ; i++) { if (freq[i] != 0) { result = i; freq[i]--; break; } } // result = 1 // arrange all remaining digits // in ascending order for (let i = 0 ; i <= 9 ; i++) { while (freq[i]-- != 0){ result = result * 10 + i; } }
 //10 //100 //1005 //10055 //10055 return result*/

Complejidad del tiempo: O (nlogn).

Complejidad espacial: O (1).

Explicación de la complejidad del tiempo y el espacio

Estamos eliminando cada dígito del número e incrementando su conteo respectivo en una matriz que tomará O (logn). Luego, encontramos el número distinto de cero más pequeño de la matriz en O (10).

Después de eso, estamos reorganizando los dígitos para crear el número más pequeño en O (10 * logn). La complejidad del tiempo es O (logn + 10+ 10logn) = O (logn) u O (d), donde d es el número de dígitos

Estamos usando un espacio constante (una matriz de 10 números), por lo que la complejidad del espacio es O (1).

Si te gustó este artículo, dale un poco y compártelo! Si tiene alguna pregunta relacionada con esto, no dude en preguntarme.

For more like this and algorithmic solutions in Javascript, follow me on Twitter. I write about ES6, React, Nodejs, Data structures, and Algorithms on learnersbucket.com.