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代码
