当前位置:网站首页>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
边栏推荐
- If you start from zero according to the frame
- C listens for WMI events
- 双指针进阶--leetcode题目--盛最多水的容器
- C语言程序设计之函数的构造
- [batch change MySQL table and corresponding codes of fields in the table]
- Solution of Navicat connecting Oracle library is not loaded
- [二叉数] 二叉树的最大深度+N叉树的最大深度
- How to sort the numbers with text in Excel from small to large instead of the first number
- 1-5 nodejs commonjs specification
- matlab如何绘制已知公式的曲线图,Excel怎么绘制函数曲线图像?
猜你喜欢
Why do some people say SCM is simple and I have to learn it so hard?
Simulation of infrared wireless communication based on 51 single chip microcomputer
PC电脑使用无线网卡连接上手机热点,为什么不能上网
ASP. NET CORE3. 1. Solution to login failure after identity registers users
[difference between Oracle and MySQL]
2. Electron's HelloWorld
Using quartz under. Net core -- job attributes and exceptions of [4] jobs and triggers
Signalr can actively send data from the server to the client
快时钟同步慢时钟域下的异步控制信号slow clk to fast clk
HCIP第五次实验
随机推荐
1-5 nodejs commonjs specification
How to manually implement the mechanism of triggering garbage collection in node
QT modification UI does not take effect
Shell-入门、变量、以及基本的语法
Websocket (basic)
[difference between Oracle and MySQL]
The system cannot be started after AHCI is enabled
C dapper basically uses addition, deletion, modification and query transactions, etc
Open futures, open an account, cloud security or trust the software of futures companies?
Promise (IV)
Header built-in object
[PROJECT] small hat takeout (8)
Shell - introduction, variables, and basic syntax
Shell-cut命令的使用
RPC核心概念理解
[二叉数] 二叉树的最大深度+N叉树的最大深度
Manually implement simple promise and its basic functions
1-2 characteristics of nodejs
Understanding of RPC core concepts
Learning record of uni app dark horse yougou project (Part 2)