当前位置:网站首页>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
边栏推荐
- Ouvrir des contrats à terme, ouvrir des comptes en nuage ou faire confiance aux logiciels des sociétés à terme?
- How to change input into text
- QT modification UI does not take effect
- In ancient Egypt and Greece, what base system was used in mathematics
- Bottom processing of stack memory in browser
- [registration] tf54: engineer growth map and excellent R & D organization building
- Shell-入门、变量、以及基本的语法
- Baidu Map Case - modify map style
- 双指针进阶--leetcode题目--盛最多水的容器
- Entity Framework core captures database changes
猜你喜欢
uni-app黑马优购项目学习记录(下)
为什么有些人说单片机简单,我学起来这么吃力?
C# Task. Delay and thread The difference between sleep
Solution architect's small bag - 5 types of architecture diagrams
Clickhouse table engine
Using quartz under. Net core -- operation transfer parameters of [3] operation and trigger
Webapi + form form upload file
Flash project cross domain interception and DBM database learning [Baotou cultural and creative website development]
On lambda powertools typescript
练习:求偶数和、阈值分割和求差( list 对象的两个基础小题)
随机推荐
基于51单片机红外无线通讯仿真
.Net Core3. 1 use razorengine NETCORE production entity generator (MVC web version)
. net cross platform principle (Part I)
1-1 NodeJS
Change Oracle to MySQL
双指针进阶--leetcode题目--盛最多水的容器
matlab如何绘制已知公式的曲线图,Excel怎么绘制函数曲线图像?
Tdan over half
El cascade and El select click elsewhere to make the drop-down box disappear
El date picker limits the selection range from the current time to two months ago
Learning record of uni app dark horse yougou project (Part 2)
Devexpress GridView add select all columns
The system cannot be started after AHCI is enabled
1-3 components and modules
JS failed to change all variables and changed to the return method. Finally, the problem was solved
How to change input into text
Entity Framework core captures database changes
Flash project cross domain interception and DBM database learning [Baotou cultural and creative website development]
Scope and scope chain in JS
ASP. NET CORE3. 1. Solution to login failure after identity registers users