[数据结构与算法]2022-02-05：字典序的第K小数字。 给定整数 n 和 k，找到 1 到 n 中字典序第 k 小的数字。 注意：1 ≤ k ≤ n ≤ 10**9。 示例 : 输入: n: 13 k: 2

2022-02-05：字典序的第K小数字。
给定整数 n 和 k，找到 1 到 n 中字典序第 k 小的数字。
注意：1 ≤ k ≤ n ≤ 10**9。
示例 :
输入:
n: 13 k: 2
输出:
10
解释:
字典序的排列是 [1, 10, 11, 12, 13, 2, 3, 4, 5, 6, 7, 8, 9]，所以第二小的数字是 10。
力扣440。

答案2022-02-05：

这道题很难想到。具体见代码。
划分成左，中，右三部分。
时间复杂度：O(logN)。这道题在leetcode上，所有题解都只能做到O( (logN) 平方)的解。

代码用golang编写。代码如下：

package main

import "fmt"

func main() {
    n := 13
    k := 2
    ret := findKthNumber(n, k)
    fmt.Println(ret)
}

var offset = []int{0, 1, 10, 100, 1000, 10000, 100000, 1000000, 10000000, 100000000, 1000000000}
var number = []int{0, 1, 11, 111, 1111, 11111, 111111, 1111111, 11111111, 111111111, 1111111111}

func findKthNumber(n, k int) int {
    // 数字num，有几位，len位
    // 65237, 5位，len = 5
    len0 := lenf(n)
    // 65237, 开头数字，6，first
    first := n / offset[len0]
    // 65237，左边有几个？
    left := (first - 1) * number[len0]
    pick := 0
    already := 0
    if k <= left {
        // k / a 向上取整-> (k + a - 1) / a
        pick = (k + number[len0] - 1) / number[len0]
        already = (pick - 1) * number[len0]
        return kth((pick+1)*offset[len0]-1, len0, k-already)
    }
    mid := number[len0-1] + (n % offset[len0]) + 1
    if k-left <= mid {
        return kth(n, len0, k-left)
    }
    k -= left + mid
    len0--
    pick = (k+number[len0]-1)/number[len0] + first
    already = (pick - first - 1) * number[len0]
    return kth((pick+1)*offset[len0]-1, len0, k-already)
}

func lenf(n int) int {
    len0 := 0
    for n != 0 {
        n /= 10
        len0++
    }
    return len0
}

func kth(max int, len0 int, kth0 int) int {
    // 中间范围还管不管的着！
    // 有任何一步，中间位置没命中，左或者右命中了，那以后就都管不着了！
    // 但是开始时，肯定是管的着的！
    closeToMax := true
    ans := max / offset[len0]
    for dinc(kth0) > 0 {
        kth0--
        max %= offset[len0]
        len0--
        pick := 0
        if !closeToMax {
            pick = (kth0 - 1) / number[len0]
            ans = ans*10 + pick
            kth0 -= pick * number[len0]
        } else {
            first := max / offset[len0]
            left := first * number[len0]
            if kth0 <= left {
                closeToMax = false
                pick = (kth0 - 1) / number[len0]
                ans = ans*10 + pick
                kth0 -= pick * number[len0]
                continue
            }
            kth0 -= left
            mid := number[len0-1] + (max % offset[len0]) + 1
            if kth0 <= mid {
                ans = ans*10 + first
                continue
            }
            closeToMax = false
            kth0 -= mid
            len0--
            pick = (kth0+number[len0]-1)/number[len0] + first
            ans = ans*10 + pick
            kth0 -= (pick - first - 1) * number[len0]
        }
    }
    return ans
}

执行结果如下：

左神java代码