[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

上一篇:POC完成步入落地阶段,民生保险区块链项目谈如何回归业务本质


下一篇:人工智能的市场驱动因素、制约因素和机会