C++ 解法, 执行用时: 3ms, 内存消耗: 404KB, 提交时间: 2022-08-06

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param n int整型 
     * @param k int整型 
     * @return int整型
     */
    int findKth(int n, int k) {
        // write code here
        int cur=1;
        --k;
        while(k>0)
        {
            long step=0,first=cur,last=cur+1;
            while(first<=n)
            {
                step+=min(last,(long)(n+1))-first;
                first*=10;
                last*=10;
            }
            if(step<=k)
            {
                k-=step;
                cur++;
            }
            else{
                k--;
                cur*=10;
            }
        }
        return cur;
    }
};

C++ 解法, 执行用时: 3ms, 内存消耗: 408KB, 提交时间: 2022-03-15

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param n int整型 
     * @param k int整型 
     * @return int整型
     */
    int findKth(int n, int k) {
        // write code here
        int cur = 1;
        --k;
        while (k > 0) {
            long step = 0, first = cur, last = cur + 1;
            while (first <= n) {
                step += min(last, (long)(n + 1)) - first;
                first *= 10;
                last *= 10;
            }
            if (step <= k) {
                k -= step;
                cur++;
            }
            else {
                k--;
                cur *= 10;
            }
        }
        return cur;
    }
};

C++ 解法, 执行用时: 3ms, 内存消耗: 444KB, 提交时间: 2022-07-30

class Solution {
private:
    // 确定指定前缀下所有子节点数
    long getCount(long prefix, long n) {
        long cur=prefix;
        long next=prefix+1; // 下一个前缀
        long count=0;
        while (cur<=n) {
            count+=min(n+1, next)-cur;
            cur*=10;
            next*=10;
        }
        return count;
    }
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param n int整型 
     * @param k int整型 
     * @return int整型
     */
    int findKth(int n, int k) {
        // write code here
        long p=1; // 第一字典序是1
        long prefix=1; // 前缀
        while (p<k) {
            long count=getCount(prefix, n);
            if (p+count>k) {
                // 说明第k个数, 在这个前缀范围里面
                prefix*=10;
                p++;
            }
            else {
                // 说明第k个数不在这个前缀范围里面, 前缀需要扩大1
                prefix++;
                p+=count;
            }
        }
        return prefix;
    }
};

C++ 解法, 执行用时: 4ms, 内存消耗: 396KB, 提交时间: 2022-05-09

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param n int整型 
     * @param k int整型 
     * @return int整型
     */
    int findKth(int n, int k) {
        // write code here
        long long cur = 1;
        k -= 1;
        while(k > 0) {
            long num = 0;
            long left = cur, right = cur + 1;
            while (left <= n) {
                num += min(long(n + 1), right) - left;
                left = left * 10;
                right = right * 10;
            }
            if (num <= k) {
                k -= num;
                cur += 1;
            } else {
                k -= 1;
                cur = cur * 10;
            }
        }
        return cur;
    }
};

C++ 解法, 执行用时: 4ms, 内存消耗: 400KB, 提交时间: 2022-06-24

class Solution {
  public:
    int findKth(int n, int k) {
        int num = 1;
        --k;
        while (k > 0) {
            long c = 0, a = num, b = num + 1;
            while (a <= n) {
                c += min(b, (long)(n + 1)) - a;
                a *= 10;
                b *= 10;
            }
            if (c <= k) {
                k -= c;
                num++;
            } else {
                k--;
                num *= 10;
            }
        }
        return num;
    }
};