Πώς να σχηματίσετε τον μικρότερο δυνατό αριθμό από έναν δεδομένο αριθμό σε JavaScript

Σε αυτό το σεμινάριο, θα εφαρμόσουμε έναν αλγόριθμο για να σχηματίσουμε τον μικρότερο δυνατό αριθμό με ES6.

Input: 55010 7652634
Output: 10055 2345667

Σημείωση : Ο μετασχηματισμένος αριθμός δεν πρέπει να ξεκινά με 0 εάν έχει τουλάχιστον έναν μη μηδενικό χαρακτήρα.

Θα χρησιμοποιήσουμε δύο διαφορετικές προσεγγίσεις για να λύσουμε αυτό το πρόβλημα. Όλα θα γραφτούν στο ES6.

  • Στην πρώτη προσέγγιση, θα υποθέσουμε ότι ο παρεχόμενος αριθμός είναι σε μορφή συμβολοσειράς και θα το λύσουμε χρησιμοποιώντας ταξινόμηση που θα πάρει O (nlogn).
  • Στη δεύτερη προσέγγιση, θα λύσουμε με αριθμητική τιμή με το O (d) χρόνο, όπου d είναι ο αριθμός των ψηφίων.

Χρησιμοποιώντας την ταξινόμηση O (nlogn).

Εκτέλεση

  • Θα μετατρέψουμε τον αριθμό σε πίνακα χαρακτήρων και μετά θα ταξινομήσουμε αυτόν τον πίνακα.
  • Μετά την ταξινόμηση θα ελέγξουμε εάν ο πρώτος χαρακτήρας του πίνακα είναι 0.
  • Εάν δεν είναι 0 τότε θα ενταχθούμε στον πίνακα και θα τον επιστρέψουμε.
  • Εάν είναι 0 τότε θα βρούμε τον πρώτο μη μηδενικό αριθμό και θα τον αλλάξουμε με 0 και θα τον επιστρέψουμε.
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(''); }

Εκτέλεση του προγράμματος

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('');*/

Πως δουλεύει

Δημιουργήσαμε αρχικά τη σειρά χαρακτήρων όπως ['5', '5', '0', '1', 0]. Στη συνέχεια το ταξινομούμε σε ['0', '0', '1', '5', '5']Μετά από αυτό, βρίσκουμε το πρώτο μη μηδενικό στοιχείο και το αλλάζουμε με πρώτα μηδενικά στοιχεία όπως ['1', '0', '0', '5', '5']. Τώρα έχουμε τον μικρότερο αριθμό μας έτοιμος, απλώς πρέπει να τους συνδυάσουμε και να τον επιστρέψουμε.

Μάθετε περισσότερα σχετικά με το διαχωρισμό (), ταξινόμηση (), συμμετοχή ().

Πολυπλοκότητα χρόνου: O (nlogn).

Διαστημική πολυπλοκότητα: O (n).

Επεξήγηση πολυπλοκότητας χρόνου και χώρου

Δημιουργούμε έναν πίνακα χαρακτήρων που θα διαρκέσει O (n) χρόνο. Στη συνέχεια, η ταξινόμηση του πίνακα θα πάρει O (nlogn).

Μετά από αυτό, βρίσκουμε τον δείκτη του μικρότερου μη μηδενικού αριθμού που μπορεί να πάρει το O (n) στη χειρότερη περίπτωση και ενώνοντας τον πίνακα για να δημιουργήσουμε τη συμβολοσειρά θα πάρει το O (n). Καθώς όλες αυτές οι λειτουργίες εκτελούνται το ένα μετά το άλλο. Επομένως, η πολυπλοκότητα του χρόνου είναι O (n + nlogn + n + n) = O (nlogn).

Δημιουργούμε μια σειρά χαρακτήρων από τη συμβολοσειρά, επομένως η πολυπλοκότητα του χώρου είναι O (n).

Χρησιμοποιώντας την αριθμητική τιμή O (logn).

Υπάρχει ένα μειονέκτημα σε αυτήν την προσέγγιση: εάν ο αριθμός περιέχει μόνο μηδενικά τότε θα επιστρέψει ένα μηδέν.

Εκτέλεση

  • Θα δημιουργήσουμε μια σειρά αριθμών από 0 έως 9.
  • Στη συνέχεια, θα παρακολουθούμε τα ψηφία που υπάρχουν στον αριθμό αυξάνοντας τον αριθμό τους στον πίνακα.
  • Μετά από αυτό, θα βρούμε το μικρότερο μη μηδενικό ψηφίο και θα μειώσουμε τον αριθμό του κατά 1.
  • Στο τέλος, θα αναδημιουργήσουμε τον αριθμό τοποθετώντας τους σε αύξουσα σειρά και θα επιστρέψουμε το αποτέλεσμα.
  • Αυτή η λύση βασίζεται στο είδος καταμέτρησης.
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; }

Εκτέλεση του προγράμματος

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*/

Πολυπλοκότητα χρόνου: O (nlogn).

Διαστημική πολυπλοκότητα: O (1).

Επεξήγηση πολυπλοκότητας χρόνου και χώρου

Αφαιρούμε κάθε ψηφίο από τον αριθμό και αυξάνουμε τον αντίστοιχο αριθμό σε έναν πίνακα που θα παίρνει το O (logn). Στη συνέχεια, βρίσκουμε τον μικρότερο μη μηδενικό αριθμό από τον πίνακα στο O (10).

Μετά από αυτό αναδιατάσσουμε τα ψηφία για να δημιουργήσουμε τον μικρότερο αριθμό στο O (10 * logn). Η πολυπλοκότητα του χρόνου είναι O (logn + 10+ 10logn) = O (logn) ή O (d), όπου d είναι ο αριθμός των ψηφίων

Χρησιμοποιούμε σταθερό χώρο (μια σειρά από 10 αριθμούς), επομένως η πολυπλοκότητα του διαστήματος είναι O (1).

Εάν σας άρεσε αυτό το άρθρο, δώστε το λίγο; Εάν έχετε οποιεσδήποτε ερωτήσεις σχετικά με αυτό, μη διστάσετε να με ρωτήσετε.

Για περισσότερες παρόμοιες και αλγοριθμικές λύσεις στο Javascript, ακολουθήστε με στο Twitter . Γράφω για ES6, React, Nodejs, δομές δεδομένων και αλγόριθμους στο learnersbucket.com .