字典序的第K小数字
难度:
标签:
题目描述
给定整数 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
提示:
1 <= k <= n <= 109
代码结果
运行时间: 24 ms, 内存: 16.0 MB
/*
* 思路：
* 使用Java Stream流的方式计算。
* 我们首先生成从1到n的范围内的整数流，然后使用sorted对其进行字典序排序。
* 取第k个元素即可。
*/
import java.util.stream.IntStream;
public class Solution {
public int findKthNumber(int n, int k) {
return IntStream.rangeClosed(1, n)
.mapToObj(String::valueOf)
.sorted()
.mapToInt(Integer::parseInt)
.skip(k - 1)
.findFirst()
.getAsInt();
}
}解释
方法:
这个题解使用了一种巧妙的方法来找到字典序第k小的数字。主要思路是：从1开始，通过计算当前前缀下所有数字的个数，判断第k个数字是否在当前前缀下。如果在当前前缀下，则第k个数字的第一位就是当前前缀；如果不在，则将前缀加1，继续查找下一个前缀。重复这个过程，直到找到第k个数字。
时间复杂度:
O((log n)^2)
空间复杂度:
O(1)
代码细节讲解
🦆
解法中提到的'前缀'是具体指什么？在字典序问题中，前缀如何影响数字的排列？
▷🦆
在计算每个前缀下的数字个数时，为什么使用区间[interval[0], interval[1])的方式，并且每次区间扩大10倍？
▷🦆
为何在确定k不在当前前缀下时，选择将前缀加1而不是其他操作？这样的操作对于缩小查找范围有什么特殊的意义吗？
▷🦆
当确定第k个数字在当前前缀下时，为什么要将结果乘以10，并将k减去1，而不是直接减去cnt？这样做的目的是什么？
▷