2022-02-05: the k-th decimal number of dictionary order. Given integers n and K, find 1

2022-02-05： The second part of the dictionary order K Small number .

Given integer n and k, find 1 To n Chinese dictionary order No k Small numbers .

Be careful ：1 ≤ k ≤ n ≤ 10**9.

Example :

Input :

n: 13 k: 2

Output :

10

explain :

The order of the dictionary is 1, 10, 11, 12, 13, 2, 3, 4, 5, 6, 7, 8, 9, So the second smallest number is 10.

Power button 440.

answer 2022-02-05：

This problem is hard to think of . See code for details .

Divide into left , in , The third part on the right .

Time complexity ：O(logN). The question is leetcode On , All the solutions can only be done O( (logN) square ) Solution .

The code to use golang To write . The code is as follows ：

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 {
    //  Numbers num, How many are there ,len position 
    // 65237, 5 position ,len = 5
    len0 := lenf(n)
    // 65237,  Beginning number ,6,first
    first := n / offset[len0]
    // 65237, There are a few on the left ？
    left := (first - 1) * number[len0]
    pick := 0
    already := 0
    if k <= left {
        // k / a  Rounding up -> (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 {
    //  The middle range doesn't matter ！
    //  Any step , Missed in the middle , Left or right hit , After that, I can't control it ！
    //  But at first , It must be in charge ！
    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
}

The results are as follows ：

picture

---

Zuo Shen java Code