企业微网站建站,网站名字重复,做网站可以用哪些语言,江苏哪家做网站排名比较好给你一个整数 n #xff0c;按字典序返回范围 [1, n] 内所有整数。 你必须设计一个时间复杂度为 O(n) 且使用 O(1) 额外空间的算法。 示例 1#xff1a; 输入#xff1a;n 13 输出#xff1a;[1,10,11,12,13,2,3,4,5,6,7,8,9] 示例 2#xff1a; 输入#xff1a;n 2 输… 给你一个整数 n 按字典序返回范围 [1, n] 内所有整数。 你必须设计一个时间复杂度为 O(n) 且使用 O(1) 额外空间的算法。 示例 1 输入n 13 输出[1,10,11,12,13,2,3,4,5,6,7,8,9] 示例 2 输入n 2 输出[1,2] 提示
1 n 5 * 10^4 解题思路
1、正常的排序时间复杂度都大于O(n)显然排序不行
2、既然排序不行那可以按顺序创造数字存储不错的方向
3、因为要求字典序所以能添0尽可能添加0边界为最后一个数是9或者此数大于n
代码:
class Solution {public ListInteger lexicalOrder(int n) {ListInteger res new ArrayList();int number 1;for(int i 0; i n; i ) {//取n个数res.add(number);if(number * 10 n) {//优先添0number number * 10;}else {while(number % 10 9 || number 1 n) number number / 10;//已经到边界了number ;}}return res;}
}
