当前位置:网站首页>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
边栏推荐
- 1-4 configuration executable script of nodejs installation
- EF core in ASP Generate core priority database based on net entity model
- In ancient Egypt and Greece, what base system was used in mathematics
- Baidu Map Case - Zoom component, map scale component
- 【生活中的逻辑谬误】稻草人谬误和无力反驳不算证明
- Clickhouse SQL operation
- Shell-入门、变量、以及基本的语法
- Use of shell cut command
- Future 用法详解
- How to manually implement the mechanism of triggering garbage collection in node
猜你喜欢
Collection of common SQL statements
Use of todesk remote control software
Advantages and disadvantages of several note taking software
[logical fallacy in life] Scarecrow fallacy and inability to refute are not proof
Simulation of infrared wireless communication based on 51 single chip microcomputer
Tdan over half
Using quartz under. Net core -- operation transfer parameters of [3] operation and trigger
Compare the performance of query based on the number of paging data that meet the query conditions
C# Task. Delay and thread The difference between sleep
Use between nodejs modules
随机推荐
Change Oracle to MySQL
Oninput one function to control multiple oninputs (take the contents of this input box as parameters) [very practical, very practical]
Router object, route object, declarative navigation, programmed navigation
On lambda powertools typescript
ASP. Net core configuration options (Part 1)
. net type transfer
Generating access keys using JSON webtoken
ASP. NET CORE3. 1. Solution to login failure after identity registers users
Header built-in object
ECMAScript history
How to use the input table one-way service to send (occupy less) picture files (body transmission)? FileReader built-in object involved
tidb-server 的配置文件在哪里?
Self use learning notes - connectingstring configuration
读《Software Engineering at Google》(15)
Indexes and views in MySQL
Use of Shell sort command
快时钟同步慢时钟域下的异步控制信号slow clk to fast clk
ClickHouse-数据类型
Understanding and small examples of unity3d object pool
2.Electron之HelloWorld