golang 解法, 执行用时: 0 ms, 内存消耗: 1.8 MB, 提交时间: 2023-06-09 15:49:55

func findKthNumber(n int, k int) int {
    var dfs func(l, r int) int
    dfs = func(l, r int) int {
        if l > n {
            return 0
        }
        if r > n {
            r = n
        }
        return r - l + 1 + dfs(l * 10, r * 10 + 9)
    }

    cur := 1
    k--
    for k > 0 {
        cnts := dfs(cur, cur)
        if cnts <= k {
            k -= cnts
            cur++
        } else {
            k--
            cur *= 10
        }
    }
    return cur
}

java 解法, 执行用时: 0 ms, 内存消耗: 38.1 MB, 提交时间: 2023-06-09 15:49:14

class Solution {
    public int findKthNumber(int n, int k) {
        int cur = 1;
        k--;
        while(k > 0) {
            long cnts = dfs(cur, cur, n);
            if(cnts <= k) {
                k -= cnts;
                cur++;
            } else {
                k--;
                cur *= 10;
            }
        }
        return cur;
    }

    private long dfs(long l, long r, int n) {
        if(l > n)
            return 0;
        return Math.min(r, n) - l + 1 + dfs(l * 10, r * 10 + 9, n);
    }
}

python3 解法, 执行用时: 48 ms, 内存消耗: 16.1 MB, 提交时间: 2023-06-09 15:49:00

class Solution:
    def findKthNumber(self, n: int, k: int) -> int:
        # 小于等于n的以1开头的数有多少个?
        # 1 10-19 100-199 1000-1999 = 1111
        def dfs(l, r):
            # 当前层有 r - l + 1 个节点可取，递归到下一层。
            # l * 10： 从10变成100， r * 10 + 9: 从19变成199
            return 0 if l > n else min(n, r) - l + 1 + dfs(l * 10, r * 10 + 9)
        
        cur = 1
        k -= 1
        while k:
            cnts = dfs(cur, cur)
            # 当前节点中总数都小于需要的数，可以全部取走，bfs到同层下一点 (比如 1 -> 2)
            if cnts <= k:
                k -= cnts
                cur += 1
            # 答案在当前节点的子节点中，取走当前根节点，dfs向下 (比如 1 -> 10)
            else:
                k -= 1
                cur *= 10
        return cur

javascript 解法, 执行用时: 68 ms, 内存消耗: 40.9 MB, 提交时间: 2023-06-09 15:48:33

/**
 * @param {number} n
 * @param {number} k
 * @return {number}
 */
var findKthNumber = function(n, k) {
    let curr = 1;
    k--;
    while (k > 0) {
        const steps = getSteps(curr, n);
        if (steps <= k) {
            k -= steps;
            curr++;
        } else {
            curr = curr * 10;
            k--;
        }
    }
    return curr;
}

const getSteps = (curr, n) => {
    let steps = 0;
    let first = curr;
    let last = curr;
    while (first <= n) {
        steps += Math.min(last, n) - first + 1;
        first = first * 10;
        last = last * 10 + 9;
    }
    return steps;
};

golang 解法, 执行用时: 4 ms, 内存消耗: 1.8 MB, 提交时间: 2023-06-09 15:48:04

func getSteps(cur, n int) (steps int) {
    first, last := cur, cur
    for first <= n {
        steps += min(last, n) - first + 1
        first *= 10
        last = last*10 + 9
    }
    return
}

func findKthNumber(n, k int) int {
    cur := 1
    k--
    for k > 0 {
        steps := getSteps(cur, n)
        if steps <= k {
            k -= steps
            cur++
        } else {
            cur *= 10
            k--
        }
    }
    return cur
}

func min(a, b int) int {
    if a > b {
        return b
    }
    return a
}

python3 解法, 执行用时: 52 ms, 内存消耗: 16 MB, 提交时间: 2023-06-09 15:47:40

class Solution:
    def getSteps(self, cur: int, n: int) -> int:
        steps, first, last = 0, cur, cur
        while first <= n:
            steps += min(last, n) - first + 1
            first *= 10
            last = last * 10 + 9
        return steps

    def findKthNumber(self, n: int, k: int) -> int:
        cur = 1
        k -= 1
        while k:
            steps = self.getSteps(cur, n)
            if steps <= k:
                k -= steps
                cur += 1
            else:
                cur *= 10
                k -= 1
        return cur

java 解法, 执行用时: 0 ms, 内存消耗: 38.1 MB, 提交时间: 2023-06-09 15:47:08

class Solution {
    public int findKthNumber(int n, int k) {
        int curr = 1;
        k--;
        while (k > 0) {
            int steps = getSteps(curr, n);
            if (steps <= k) {
                k -= steps;
                curr++;
            } else {
                curr = curr * 10;
                k--;
            }
        }
        return curr;
    }

    public int getSteps(int curr, long n) {
        int steps = 0;
        long first = curr;
        long last = curr;
        while (first <= n) {
            steps += Math.min(last, n) - first + 1;
            first = first * 10;
            last = last * 10 + 9;
        }
        return steps;
    }
}