题目描述
给定一个整数 n, 返回从 1 到 n 的字典顺序。
例如,给定 n = 13,返回 [1,10,11,12,13,2,3,4,5,6,7,8,9] 。
请尽可能的优化算法的时间复杂度和空间复杂度。输入的数据 n 小于等于 5,000,000。
题解
排序法
首先把 1 到 n 所有整数的字符串形式放进数组,然后对这个字符串数组进行排序,最后把所有字符串转换成对应的整数就行了。
时间复杂度是 ,空间复杂度是 。
字典树法
还可以按从小到大顺序直接生成所有整数,首先观察如下的字典树:
字典树
可以看出来,这是一棵 10 叉的字典树,第一层根节点,第二层没有 0 (因为不能有前导 0 ),后面的每一层都是在上一层的基础上添加一位 0 到 9 。
而如果按照前序遍历的顺序遍历这棵树,得到的整数序列就是字典序从小到大的。但是这棵树深度是没有限制的啊,所以如果遍历到的数字 x 大于 n 的话,就要结束遍历,回溯到上一层。
时间复杂度是 ,空间复杂度是 。
代码
排序法(c++)
classSolution { public: vector<int>lexicalOrder(intn) { vector<string>s; vector<int>res; for (inti=1; i<=n; ++i) s.push_back(to_string(i)); sort(s.begin(), s.end()); for (inti=0; i<n; ++i) { res.push_back(atoi(s[i].c_str() ) ); } returnres; } };
排序法(python)
classSolution: deflexicalOrder(self, n: int) ->List[int]: res= [] foriinrange(1, n+1): res.append(str(i) ) res.sort() res= [int(x) forxinres] returnres
字典树法(c++)
classSolution { public: vector<int>lexicalOrder(intn) { vector<int>res; for (inti=1; i<=9; ++i) dfs(i, n, res); returnres; } voiddfs(intx, intn, vector<int>&res) { if (x>n) return; res.push_back(x); for (inti=0; i<=9; ++i) { dfs(x*10+i, n, res); } } };
字典树法(python)
classSolution: deflexicalOrder(self, n: int) ->List[int]: res= [] foriinrange(1, 10): self.dfs(i, n, res) returnresdefdfs(self, x, n, res): ifx>n: returnres.append(x) foriinrange(10): self.dfs(x*10+i, n, res)
后记
字典序法的递归需要耗费更大的空间,而在实际运行中, python 代码排序法的运行速度甚至比字典序法更快,这说明了 python 递归是真的慢。
作者简介:godweiyang,知乎同名,华东师范大学计算机系硕士在读,方向自然语言处理与深度学习。喜欢与人分享技术与知识,期待与你的进一步交流~