字典序的第K小数字

题目描述：

给定整数 n 和 k，返回 [1, n] 中字典序第 k 小的数字。

示例 1:

输入: n = 13, k = 2
输出: 10
解释: 字典序的排列是 [1, 10, 11, 12, 13, 2, 3, 4, 5, 6, 7, 8, 9]，所以第二小的数字是 10。
示例 2:

输入: n = 1, k = 1
输出: 1

提示:

1 <= k <= n <= 109

思路:

时间复杂度：O(),空间复杂度O(1)

从1到9依次计算，就是得到以1为开始数字，计算出以1开头的数字的个数，如果k比这个大就k-=cnt，如果不大就i*10开始依次计算。

代码:

func count(n ,cur int)int{
    l,r := cur,cur
    cnt := 0
    for l <= n{
        cnt += min(n, r)-l+1
        l *= 10
        r = r*10 +9
    }
    return cnt
}

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

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

代码效率：

执行用时：0 ms, 在所有 Go 提交中击败了100.00%的用户
内存消耗：1.9 MB, 在所有 Go 提交中击败了46.43%的用户