Given an integer N, type numbers from 1 to N in lexicographic order

Question

I try to print numbers from 1 to N in lexicographical order, but I get unsuccessful output. for the next input 100, I get 100, but its shift and it does not correspond to the expected result, there is an error in my code, but I can not restore it.

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

Think about when i=1, j=10what will happen in

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

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

Yes, there resultwill be push_back 10 (0 + 10 * 1), 11 (1 + 10 * 1), 12 (2 + 10 * 1) .. Here is the solution:

#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 2

You iterate over all 2-digit numbers, starting with 1, before printing the first 3-digit number, so your approach will not work.

- 11, , 3. 0 , 1 0, 2 1 .. , , , n, 10. , . , , , n. 10.

, O (1) , , :

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 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;
    }
}

, valid_spaces .

, base11 → base 10 , O (N) - while :

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;
}

, - N .

Answer 3

, ?

#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;
}

lexicalLess(...) :

#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);
}

Boost .

Answer 4

- , std::sort , , .

• , , .
• . .
• strs.4. strs
  

#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;
    }
    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;
    }
}

Answer 5

1 n, n , . set , . , :

 void lexicographicalOrder(int n){
     set<string> ans;
     for(int i = 1; i <= n; i++)
        ans.insert(to_string(i));
     for(auto ele : ans)
        cout <<ele <<"\n";
 }