当前位置:网站首页>386. 字典序排数(中等)-迭代-全排列
386. 字典序排数(中等)-迭代-全排列
2022-04-23 17:32:00 【hequnwang10】
一、题目描述
给你一个整数 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]
二、解题
迭代
共有 n 个数需要被处理,假设当前处理到的数为 j,根据字典序规则,在满足条件的前提下,我们优先在 j 的后面添加 0(即 j * 10 < n 满足),否则我们考虑将上一位回退并进行加一操作。
class Solution {
public List<Integer> lexicalOrder(int n) {
//迭代
List<Integer> res = new ArrayList<>();
int number = 1;
for(int i = 0;i<n;i++){
res.add(number);
//首先尝试在number后面加0
if(number * 10 <= n){
number *= 10;
}else{
//如果加0后大于n了,则每次只加1.当然也需要判断是否进位 比如19,29,39。。。达到进位要求然后回退上一位。
while( number % 10 == 9 || number+1>n){
number /= 10;
}
number++;
}
}
return res;
}
}
时间复杂度:O(n);
空间复杂度:O(1)。
版权声明
本文为[hequnwang10]所创,转载请带上原文链接,感谢
https://blog.csdn.net/hequnwang10/article/details/124355525
边栏推荐
- Future 用法详解
- 2. Electron's HelloWorld
- ASP. Net core configuration options (Part 1)
- .Net Core3. 1 use razorengine NETCORE production entity generator (MVC web version)
- freeCodeCamp----shape_ Calculator exercise
- 1-1 NodeJS
- Clickhouse table engine
- 读《Software Engineering at Google》(15)
- Use between nodejs modules
- Low code development platform sorting
猜你喜欢
Simulation of infrared wireless communication based on 51 single chip microcomputer
双闭环直流调速系统matlab/simulink仿真
How to change input into text
【生活中的逻辑谬误】稻草人谬误和无力反驳不算证明
ClickHouse-表引擎
Learning record of uni app dark horse yougou project (Part 2)
C# Task. Delay and thread The difference between sleep
[WPF binding 3] listview basic binding and data template binding
Using quartz under. Net core - [1] quick start
MySQL installation
随机推荐
ASP. Net core dependency injection service life cycle
XTask与Kotlin Coroutine的使用对比
How to manually implement the mechanism of triggering garbage collection in node
Use of Shell sort command
Net standard
Indexes and views in MySQL
Promise (III)
matlab如何绘制已知公式的曲线图,Excel怎么绘制函数曲线图像?
【WPF绑定3】 ListView基础绑定和数据模板绑定
Manually implement call, apply and bind functions
Bottom processing of stack memory in browser
How to sort the numbers with text in Excel from small to large instead of the first number
ECMAScript history
Error in v-on handler: "typeerror: cannot read property 'resetfields' of undefined"
Use of shell cut command
[markdown notes]
[PROJECT] small hat takeout (8)
给 el-dialog 增加拖拽功能
Use between nodejs modules
. net cross platform principle (Part I)