Gegeben eine ganze Zahl N, Zahlen von 1 bis N in lexikographischer Reihenfolge drucken

Question

Ich versuche, die Zahlen von 1 bis N in lexikographischer Reihenfolge zu drucken, aber ich bekomme eine fehlerhafte Ausgabe. für die folgende Eingabe 100, bekomme ich die 100, aber es verschoben und es stimmt nicht mit der erwarteten Ausgabe überein, es gibt einen Fehler in meinem Code, aber ich kann es nicht nachvollziehen.

class Solution { 
public: 
    vector<int> lexicalOrder(int n) { 
     vector<int> result; 
     for(int i = 1; i <= 9; i ++){ 
     int j = 1; 
     while(j <= n){ 
      for(int m = 0; m < j ; ++ m){ 
       if(m + j * i <= n){ 

        result.push_back(m+j*i); 
       } 
      } 
      j *= 10; 
     } 
    } 
    return result; 

    } 
}; 



Input: 
100 
Output: 
[1,10,11,12,13,14,15,16,17,18,19,100,2,20,21,22,23,24,25,26,27,28,29,3,30,31,32,33,34,35,36,37,38,39,4,40,41,42,43,44,45,46,47,48,49,5,50,51,52,53,54,55,56,57,58,59,6,60,61,62,63,64,65,66,67,68,69,7,70,71,72,73,74,75,76,77,78,79,8,80,81,82,83,84,85,86,87,88,89,9,90,91,92,93,94,95,96,97,98,99] 

Expected: 
[1,10,100,11,12,13,14,15,16,17,18,19,2,20,21,22,23,24,25,26,27,28,29,3,30,31,32,33,34,35,36,37,38,39,4,40,41,42,43,44,45,46,47 

Answer 1

Du Schleife durch alle 2-stellige Nummern beginnend mit 1, bevor der ersten 3-stellige Nummer ausgeben, so wird Ihr Ansatz nicht funktionieren.

Eine Möglichkeit besteht darin, die Ziffern in Basis 11 auszugeben, die mit führenden Leerzeichen auf die maximale Anzahl von Ziffern aufgefüllt werden, in diesem Fall 3. Ausgabe 0 als Leerzeichen, 1 als 0, 2 als 1 usw. Weisen Sie in dieser Darstellung beliebige Zahlen zurück, die Leerzeichen enthalten, oder größer als n, wenn Sie als Basisnummer interpretiert werden. Es sollte möglich sein, mehrere Zurückweisungen gleichzeitig zu überspringen, aber das ist eine unnötige Optimierung. Zähle die ausgegebenen Zahlen und stoppe, wenn sie n erreicht. Dies gibt Ihnen eine lexikographische Ordnung in der Basis 10

Beispiel-Implementierung, die O (1) Raum verwendet, in dem Sie müssen die Zahlen nicht generieren und sortiert alles nach vorne, bevor Sie ausgeben können die ersten:

void oneToNLexicographical(int n) 
{ 
    if(n < 1) return; 

    // count max digits 
    int digits = 1, m = n, max_digit11 = 1, max_digit10 = 1; 
    while(m >= 10) 
    { 
     m /= 10; digits++; max_digit11 *= 11; max_digit10 *= 10; 
    } 

    int count = 0; 
    bool found_n = false; 
    // count up starting from max_digit * 2 (first valid value with no leading spaces) 
    for(int i = max_digit11 * 2; ; i++) 
    { 
     int val = 0, trailing_spaces = 0; 
     int place_val11 = max_digit11, place_val10 = max_digit10; 
     // bool valid_spaces = true; 
     for(int d = 0; d < digits; d++) 
     { 
      int base11digit = (i/place_val11) % 11; 
      if(base11digit == 0) 
      { 
       trailing_spaces++; 
       val /= 10; 
      } 
      else 
      { 
       // if we got a non-space after a space, it's invalid 
       // if(trailing_spaces > 0) 
       // { 
       // valid_spaces = false; 
       // break; // trailing spaces only 
       // } 
       val += (base11digit - 1) * place_val10; 
      } 
      place_val11 /= 11; 
      place_val10 /= 10; 
     } 
     // if(valid_spaces && (val <= n)) 
     { 
      cout << val << ", "; 
      count++; 
     } 
     if(val == n) 
     { 
      found_n = true; 
      i += 10 - (i % 11); // skip to next number with one trailing space 
     } 

     // skip past invalid numbers: 

     // if there are multiple trailing spaces then the next run of numbers will have spaces in the middle - invalid 
     if(trailing_spaces > 1) 
      i += (int)pow(11, trailing_spaces - 1) - 1; 
     // if we have already output the max number, then all remaining numbers 
     // with the max number of digits will be greater than n 
     else if(found_n && (trailing_spaces == 1)) 
      i += 10; 

     if(count == n) 
      break; 
    } 
} 

Damit werden alle ungültigen Nummern übersprungen. Daher ist es nicht notwendig, vor der Ausgabe jeweils valid_spaces zu testen.

Die innere Schleife kann dabei die base11 entfernt werden -> Basis 10 Umrechnungsdifferenzen verwendet, so dass der Algorithmus O (N) - dem inneren While-Schleife eine konstante zustrebt:

int val = max_digit10; 
for(int i = max_digit11 * 2; ; i++) 
{ 
    int trailing_spaces = 0, pow11 = 1, pow10 = 1; 
    int j = i; 
    while((j % 11) == 0) 
    { 
     trailing_spaces++; 
     pow11 *= 11; 
     pow10 *= 10; 
     j /= 11; 
    } 

    int output_val = val/pow10;  
    if(output_val <= n) 
    { 
     cout << output_val << ", "; 
     count++; 
    } 
    if(output_val == n) 
     found_n = true; 

    if(trailing_spaces > 1) 
    { 
     i += (pow11/11) - 1; 
    } 
    else if(found_n && (trailing_spaces == 1)) 
    { 
     i += 10; 
     val += 10; 
    } 
    else if(trailing_spaces == 0) 
     val++; 

    if(count == n) 
     break; 
} 

Demonstration

Der alternative, einfachere Ansatz besteht nur darin, N Strings aus den Zahlen zu generieren und sie zu sortieren.

Answer 2

Denken Sie darüber nach, wenn i=1, j=10 was in

for(int m = 0; m < j ; ++ m){ 
       if(m + j * i <= n){ 

        result.push_back(m+j*i); 
       } 
      } 

Ja passieren wird, wird result 10 push_back (0 + 10 * 1), 11 (1 + 10 * 1), 12 (2 + 10 * 1) .. Hier ist eine Lösung:

#include <iostream> 
#include <vector> 
#include <string> 
std::vector<int> fun(int n) 
{ 
     std::vector<std::string> result; 
     for (int i = 1; i <= n; ++i) { 
      result.push_back(std::to_string(i)); 
     } 
     std::sort(result.begin(),result.end()); 
     std::vector<int> ret; 
     for (auto i : result) { 
      ret.push_back(std::stoi(i)); 
     } 
     return ret; 
} 
int main(int argc, char *argv[]) 
{ 
     std::vector<int> result = fun(100); 
     for (auto i : result) { 
      std::cout << i << ","; 
     } 
     std::cout << std::endl; 
     return 0; 
} 

Answer 3

Vielleicht allgemeinere Lösung?

#include <vector> 
#include <algorithm> 

using namespace std; 

// returns true is i1 < i2 according to lexical order 
bool lexicalLess(int i1, int i2) 
{ 
    int base1 = 1; 
    int base2 = 1; 
    for (int c = i1/10; c > 0; c/=10) base1 *= 10; 
    for (int c = i2/10; c > 0; c/=10) base2 *= 10; 
    while (base1 > 0 && base2 > 0) { 
     int d1 = i1/base1; 
     int d2 = i2/base2; 
     if (d1 != d2) return (d1 < d2); 
     i1 %= base1; 
     i2 %= base2; 
     base1 /= 10; 
     base2 /= 10; 
    } 
    return (base1 < base2); 
} 

vector<int> lexicalOrder(int n) { 
    vector<int> result; 
    for (int i = 1; i <= n; ++i) result.push_back(i); 
    sort(result.begin(), result.end(), lexicalLess); 
    return result; 
} 

Die andere Idee für lexicalLess(...) ganze Zahlen vor Vergleich zu Zeichenfolge konvertieren:

#include <vector> 
#include <algorithm> 
#include <string>  
#include <boost/lexical_cast.hpp> 

using namespace std; 

// returns true is i1 < i2 according to lexical order 
bool lexicalLess(int i1, int i2) 
{ 
    string s1 = boost::lexical_cast<string>(i1); 
    string s2 = boost::lexical_cast<string>(i2); 
    return (s1 , s2); 
} 

Sie benötigen Boost die zweite Version laufen.

Answer 4

leicht gefallen Zahlen zu implementieren sind, um Zeichenfolge zu konvertieren, so dass sie das Array von Strings mit std::sort in Algorithmus Header sortieren, die Strings in lexikographischer Reihenfolge sortiert, dann wieder Zahlen drehen

• Sie einen Vektor in Integer von ganzen Zahlen, die du lexikographisch sortieren willst, nenne sie Zahlen.
• Erstellen Sie einen anderen Vektor und füllen Sie die Zahlenfolgen im ersten Vektor. Nennen Sie es strs.
• Sorts strs array.4. Konvertieren von Strings strs Vektor auf ganze Zahlen und steckte es in Vektoren
  

Liste item

#include <cstdlib> 
#include <string> 
#include <algorithm> 
#include <vector> 
#include <iostream> 
using namespace std; 


string int_to_string(int x){ 
    string ret; 
    while(x > 0){ 
     ret.push_back('0' + x % 10); 
     x /= 10;enter code here 
    } 
    reverse(ret.begin(), ret.end()); 
    return ret; 
} 

int main(){ 
    vector<int> ints; 
    ints.push_back(1); 
    ints.push_back(2); 
    ints.push_back(100); 
    vector<string> strs; 
    for(int i = 0; i < ints.size(); i++){ 
     strs.push_back(int_to_string((ints[i]))); 
    } 
    sort(strs.begin(), strs.end()); 
    vector<int> sorted_ints; 
    for(int i = 0; i < strs.size(); i++){ 
     sorted_ints.push_back(atoi(strs[i].c_str())); 
    } 
    for(int i = 0; i < sorted_ints.size(); i++){ 
     cout<<sorted_ints[i]<<endl; 
    } 
}