首页 > 其他 > 详细

440. 字典序的第K小数字(十叉树)

时间:2020-07-08 20:41:05      阅读:65      评论:0      收藏:0      [点我收藏+]

技术分享图片

 

 

class Solution {

    // 十叉数
    public int findKthNumber(int n, int k) {
        int cur = 1;
        k--; // 初始化cur为第一个数,所以要k--
        while(k > 0) { 
            long left = cur, right = cur + 1, sum = 0; // long防止*10溢出
                                    // 计算本分支和下一个分支(本分支加一)之间总共有多少个数
            while(left <= n) {
                sum += Math.min(right, (long)n + 1) - left; // 计算每一层的个数
                left *= 10;  // 依次向下层走
                right *= 10;
            }
            if(sum > k) {  // 判断总数是否大于k若大于k肯定在本分支,所以继续向下走cur * 10
                cur *= 10;
                k--;
            } else { // 小于等于k说明在下一个分支,向右走cur++
                cur++;
                k -= sum;
            }
        }
        return cur;
    }
}

 

440. 字典序的第K小数字(十叉树)

原文:https://www.cnblogs.com/yonezu/p/13268995.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!