[leetcode/lintcode 题解] 算法面试真题详解：字典序的第K小数字

描述
给定整数n和k，找到按字典序排序的第k个最小整数，范围从1到n。
1 ≤ k ≤ n ≤ 1e9.

在线评测地址：领扣题库官网

样例1
输入：200,18
输出：114
解释：1,10,100,101,102,103,104,105,106,107,108,109,11,110,111,112,113,114，第十八个是114。

样例2
输入：13，2
输出：10
解释：按字典序排列顺序为 [1, 10, 11, 12, 13, 2, 3, 4, 5, 6, 7, 8, 9], 所以第二小的数字为10。

考点：

字符串枚举

题解：
字符串的构造类似于十叉树，用k减去子节点的个数，step表示以curr开头至curr+1开头间的字符串数量，step是否小于等于k，如果是，我们cur自增1，k减去step；如果不是，说明要求的数字在子节点中，我们此时cur乘以10，k自减1，以此类推，直到k为0推出循环，此时cur即为所求。
代码

public class Solution {
 * @param n: a integer
 * @param k: a integer
 * @return: return a integer
 public int findKthNumber(int n, int k) {
 int curr = 1;
 k = k - 1;
 while (k 0) {
 int steps = calSteps(n, curr, curr + 1);
 if (steps = k) { //如果不在当前层，减去steps
 curr += 1; 
 k -= steps; 
 else { //说明在当前层,curr*10缩小搜索范围继续查找
 curr *= 10;
 k -= 1;
 return curr;
 //use long in case of overflow
 public int calSteps(int n, long n1, long n2) { //计算curr开头和curr+1开头之间的字符串数量
 int steps = 0;
 while (n1 = n) {
 steps += Math.min(n + 1, n2) - n1; //每次加上当前的字符串数量
 n1 *= 10; //每次均扩大10倍
 n2 *= 10;
 return steps;
}

更多题解参考：九章官网solution

本文转自网络，原文链接：https://developer.aliyun.com/article/783895
本站部分内容转载于网络，版权归原作者所有，转载之目的在于传播更多优秀技术内容，如有侵权请联系QQ/微信：153890879删除，谢谢！