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 mainimport "fmt"func main() {n := 13k := 2ret := 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 = 5len0 := lenf(n)// 65237, 开头数字，6，firstfirst := n / offset[len0]// 65237，左边有几个？left := (first - 1) * number[len0]pick := 0already := 0if k <= left {// k / a 向上取整-> (k + a - 1) / apick = (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]) + 1if k-left <= mid {return kth(n, len0, k-left)}k -= left + midlen0--pick = (k+number[len0]-1)/number[len0] + firstalready = (pick - first - 1) * number[len0]return kth((pick+1)*offset[len0]-1, len0, k-already)
}func lenf(n int) int {len0 := 0for n != 0 {n /= 10len0++}return len0
}func kth(max int, len0 int, kth0 int) int {// 中间范围还管不管的着！// 有任何一步，中间位置没命中，左或者右命中了，那以后就都管不着了！// 但是开始时，肯定是管的着的！closeToMax := trueans := max / offset[len0]for dinc(kth0) > 0 {kth0--max %= offset[len0]len0--pick := 0if !closeToMax {pick = (kth0 - 1) / number[len0]ans = ans*10 + pickkth0 -= pick * number[len0]} else {first := max / offset[len0]left := first * number[len0]if kth0 <= left {closeToMax = falsepick = (kth0 - 1) / number[len0]ans = ans*10 + pickkth0 -= pick * number[len0]continue}kth0 -= leftmid := number[len0-1] + (max % offset[len0]) + 1if kth0 <= mid {ans = ans*10 + firstcontinue}closeToMax = falsekth0 -= midlen0--pick = (kth0+number[len0]-1)/number[len0] + firstans = ans*10 + pickkth0 -= (pick - first - 1) * number[len0]}}return ans
}

执行结果如下：

---

左神java代码