给定一个整数N，按字典顺序从1到N的打印数字

Question

我试图按照字典顺序打印从1到N的数字，但是我得到一个失败的输出。对于下面的输入100，我得到了100，但是它的移位并且与预期的输出不匹配，我的代码中存在一个错误，但是我无法回溯它。

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

你通过所有的2位数字环路输出前3位号码前从1开始的，所以你的方法是行不通的。

执行此操作的一种方法是输出基数为11的数字，用前导空格填充到最大位数，在此情况下为3.输出0作为空格，1作为0,2作为1等。拒绝任何在该表示中具有任何非尾随空格的数字，或者当被解释为基数10数字时，拒绝任何大于n的数字。应该可以一次跳过多个拒绝，但这是不必要的优化。保持你输出的数字的计数，并在达到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'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; 
    } 
} 

这会跳过所有无效的数字，所以在输出每个无效数字之前不需要测试valid_spaces。

内环可以通过执行base11被移除 - >底座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; 
} 

Demonstration

另一种更简单的方法是从数字中生成N个字符串并对它们进行排序。

Answer 2

想想当i=1，j=10将在

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

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

发生什么，是的，result会的push_back 10（0 + 10 * 1），11（1 + 10 * 1），12（2 + 10 * 1）.. 这里是一个解决方案：

#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

也许更通用的解决方案？

#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。
• Sort strs array.4。转换的可疑交易报告载体的字符串为整数，并把它放在载体
  

列表项

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