当前位置:网站首页>440. 字典序的第K小数字(困难)-字典树-数节点-字节跳动高频题
440. 字典序的第K小数字(困难)-字典树-数节点-字节跳动高频题
2022-04-23 17:32:00 【hequnwang10】
一、题目描述
给定整数 n 和 k,返回 [1, n] 中字典序第 k 小的数字。
示例 1:
输入: n = 13, k = 2
输出: 10
解释: 字典序的排列是 [1, 10, 11, 12, 13, 2, 3, 4, 5, 6, 7, 8, 9],所以第二小的数字是 10。
示例 2:
输入: n = 1, k = 1
输出: 1
示例 3:
输入:target = 11, nums = [1,1,1,1,1,1,1,1]
输出:0
二、解题
字典树
这题首先看386题。这题找第k小的数字,其实就是在树中找每个节点的子节点数量,然后与K值相比较。
其中以第一层第一个节点1计算,看以1为节点的下面有多少个子节点。若当前节点的子节点数大于K,则说明目标值就在该子树下面,然后一层一层往下面找,更新节点值,1->10,也需要更新K值,也就是第二次的第一个数0,然后计算该0下面有多少个子节点值,不停的执行,直到找到最终的值。
若当第一层的第一个节点1值下面的子节点的数量小于K值,说明在节点2下面找,更新K值,依次执行。
如果就在第一层的第一个节点下面,就依次每层往下找;
class Solution {
public int findKthNumber(int n, int k) {
long cur = 1;
k--;
while(k > 0){
int nodes = countNodes(n,cur);
if(k >= nodes){
k = k - nodes;
cur++;
}else{
k--;
cur *= 10;
}
}
return (int) cur;
}
public int countNodes(long n,long cur){
long total = 0;
long next = cur + 1;
while(cur <= n){
total += Math.min(n - cur + 1,next -cur);
cur *= 10;
next *= 10;
}
return (int) total;
}
}
输出测试一下:
代码:
class Solution {
public int findKthNumber(int n, int k) {
long cur = 1;
k--;
System.out.println("0->k:"+k);
while(k > 0){
int nodes = countNodes(n,cur);
System.out.println("nodes:"+nodes);
if(k >= nodes){
k = k - nodes;
System.out.println("1->k:"+k);
cur++;
System.out.println("1->cur:"+cur);
}else{
k--;
System.out.println("2->k:"+k);
cur *= 10;
System.out.println("2->cur:"+cur);
}
}
return (int) cur;
}
public int countNodes(long n,long cur){
long total = 0;
long next = cur + 1;
while(cur <= n){
//计算每一层的节点数,然后统计初始cur值下小于n的节点数
total += Math.min(n - cur + 1,next -cur);
System.out.println("total:"+total);
cur *= 10;
next *= 10;
}
return (int) total;
}
}
0->k:65
total:1
total:11
total:35
nodes:35
1->k:30
1->cur:2
total:1
total:11
nodes:11
1->k:19
1->cur:3
total:1
total:11
nodes:11
1->k:8
1->cur:4
total:1
total:11
nodes:11
2->k:7
2->cur:40
total:1
nodes:1
1->k:6
1->cur:41
total:1
nodes:1
1->k:5
1->cur:42
total:1
nodes:1
1->k:4
1->cur:43
total:1
nodes:1
1->k:3
1->cur:44
total:1
nodes:1
1->k:2
1->cur:45
total:1
nodes:1
1->k:1
1->cur:46
total:1
nodes:1
1->k:0
1->cur:47
分析:第一层第一个节点1的子节点数量为35,小于K值,则继续在节点2中查找,更新k值为30,然后节点2值下面的子节点数量为11,小于30,则继续在节点3中查找,然后更新K值为19,依次进行
版权声明
本文为[hequnwang10]所创,转载请带上原文链接,感谢
https://blog.csdn.net/hequnwang10/article/details/124350438
边栏推荐
- Use of five routing guards
- freeCodeCamp----shape_ Calculator exercise
- Using quartz under. Net core - calendar of [6] jobs and triggers
- Qt error: /usr/bin/ld: cannot find -lGL: No such file or directory
- [registration] tf54: engineer growth map and excellent R & D organization building
- Using quartz under. Net core -- operation transfer parameters of [3] operation and trigger
- Using quartz under. Net core - [1] quick start
- How to change input into text
- 常用SQL语句总结
- Manually implement call, apply and bind functions
猜你喜欢
ASP. Net core JWT certification
MySQL installation
Scope and scope chain in JS
On lambda powertools typescript
Learning record of uni app dark horse yougou project (Part 2)
ClickHouse-表引擎
ASP. Net core dependency injection service life cycle
【生活中的逻辑谬误】稻草人谬误和无力反驳不算证明
【WPF绑定3】 ListView基础绑定和数据模板绑定
快时钟同步慢时钟域下的异步控制信号slow clk to fast clk
随机推荐
C语言程序设计之函数的构造
How to use the input table one-way service to send (occupy less) picture files (body transmission)? FileReader built-in object involved
线性代数感悟之2
How to change input into text
Solution of Navicat connecting Oracle library is not loaded
[logical fallacy in life] Scarecrow fallacy and inability to refute are not proof
freeCodeCamp----shape_ Calculator exercise
Simulation of infrared wireless communication based on 51 single chip microcomputer
JS failed to change all variables and changed to the return method. Finally, the problem was solved
Webapi + form form upload file
[registration] tf54: engineer growth map and excellent R & D organization building
【WPF绑定3】 ListView基础绑定和数据模板绑定
[PROJECT] small hat takeout (8)
Node template engine (EJS, art template)
双闭环直流调速系统matlab/simulink仿真
Shell-sort命令的使用
Use of Shell sort command
If you start from zero according to the frame
Future 用法详解
Self use learning notes - connectingstring configuration