今天在刷LeetCode的时候遇见了一道题,题的要求是“给你一个整数 n ,按字典序返回范围 [1, n] 内所有整数。你必须设计一个时间复杂度为 O(n) 且使用 O(1) 额外空间的算法。”开始以为是简单的输出,提交后发现与答案相差甚多,看评论后方了解按字典序是什么意

一、何为字典序

字典序,顾名思义就知道是按照字典的顺序来排序,给你abcdefg你知道怎么排序,那12,48,68,122,45,1,25,6这些数字该怎么排序呢?是按照大小么?给你area,too,second又该如何排序呢?这就是字典序要做的。

字典序(dictionary order),又称 字母序(alphabetical order),原意是表示英文单词在字典中的先后顺序,在计算机领域中扩展成两个任意字符串的大小关系。

在字典中,单词是按照首字母在字母表中的顺序进行排列的,比如 alpha 在 beta 之前。而第一个字母相同时,会去比较两个单词的第二个字母在字母表中的顺序,比如 account 在 advanced 之前,以此类推。

在计算机领域中,这个字典序就不仅仅用来比较英文单词了,而是比较任意字符串。对于两个字符串,大小关系取决于两个字符串从左到右第一个不同字符的 ASCII 值的大小关系。比如ah1x小于ahb,而Z5小于a3。

在绝大多数语言中,都提供了比对字符串大小的功能,实际上比较的就是两个字符串的字典序。

二、解题步骤

1.1-n整数的字典序

既然知道了什么是字典序,那1-n之间的整数按照字典序该如何排列呢?

我们假设n=13;那么排序后的结果就是[1,10,11,12,13,2,3,4,5,6,7,8,9]。为什么这样排呢?首先1排在最前面是肯定没有问题的,那么根据字典序的排序规则,1开头的数字都要排在2,3,4,5等数字开的数字前面,1是一位数字,10是两位数,所以1后面是10,然后比较第二位,所以10后面是11,12,13。

2.算法

那么1-n之间的数该怎么用程序给他们排序呢。

我们来观察上面的排序,如果我们排序排到一个数字num了,那他的后一位应该是num*10,如果num*10<=n的话,比如n=100,那么就是1,10,100的顺序,可是如果这个数字大于n了呢,那分为两种情况,比如这个数字是99或者100或9也就是说num%10=9或者num+1>n了,那我们应该将num/10,为什么呢?因为这一位已经判断完了,比如11,12,13第二位判断完了那我们是不是回去,看第一位呢!另外一种情况就是num=17,18,45这种,不属于上一种情况,那直接+1就行了。


3.代码

int* lexicalOrder(int n, int* returnSize){
    int *ans=malloc(sizeof(int)*n);
    int num=1;
    for(int i=0;i<n;i++){
        ans[i]=num;
        if(num*10<=n){
            num*=10;
        }
        else{
            while(num%10==9||num+1>n){
                num/=10;
            }
            num++;
        }
    }
    *returnSize=n;
    return ans;
}

利用迭代的算法将1-n之间的整数按字典序输出