LeetCode#440字典序的第k小数字

input

• n:数字大小
• k:第k个小的数

example

input: (13,2)
output: 10
reason: [1, 10, 11, 12, 13, 2, 3, 4, 5, 6, 7, 8, 9]，10是第2小的数字

思路

• 理解数字的字典序，可以理解为一颗十叉树，根为1，子节点为10-19，根为2，子节点为20-29
• 输入k，可理解为要在数组中走的步数
• 定义5个变量，result = 1 最终结果；lastSteps = k -1 表示剩余步数；left = result 左节点;right = result+1 右节点; count = 0 记录需要跨过的节点数
• 先寻找最终走到终点的范围在哪，也就是找到不满的十叉树的根节点是谁
• 当 left <= n 时，证明最终位置在当前节点的右边或者下边
• 如果 right 比 n + 1 小，left right 各向下一层继续找，同时累计 count += min(right, n+1) - left
• 直到 left 大于 n，将累加的节点和当前剩余步数相比较
• 如果 lastSteps > count，证明 left 的子节点能全部走完，所以需要向右走一步 lastSteps -= count; result += 1;
• 如果 lastSteps <= count，证明 left 的子节点已经足够走完剩余的步数了，这时向下走一步，lastSteps--; result*=10;
• 当剩余步数为0时，result 就是最终结果

代码

class Solution {
    public void int findKthNumber(int n, int k) {
        int result = 1;
        int lastSteps = k - 1; //默认走了一步，走到第一个数
        while (lastSteps > 0) {
            long left = result; //用 long 类型，防止 n 达到 2的32次方附近时，left * 10 会溢出
            long right = result + 1;
            int count = 0;
            while(left <= n) { //向下或向右探索，计算需要跨过的节点数
                count += Math.min(right, n+1) - left;
                left *= 10;
                right *= 10;
            }
            
            if (count > lastSteps) { //节点太多，跨不过去，只能向下走一层
                lastSteps --;
                result *= 10;
            } else { //节点不足，当前剩余步数足够走完全部节点，直接跨过这个节点以及他的子节点，向右走一步
                lastSteps -= count;
                result ++;
            }
        }
        return result;
    }

}