给定整数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

在输出前 3 位数字之前，您将循环遍历所有以 1 开头的 2 位数字，因此您的方法将不起作用。

一种方法是输出以 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 -> 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 个字符串并对它们进行排序。