golang力扣leetcode 440.字典序的第K小数字

func findKthNumber(n int, k int) int {
  //prefix数字i，p位置
  prefix, p := 1, 1
  //等到p=k时，prefix就是答案
  for p < k {
    //获得以prefix开头的字典个数
    cnt := getCount(prefix, n)
    //这里减1的原因是，cnt包含i的当前位置，而p就是当前位置，所以重复计算了一个位置
    if (p + cnt - 1) >= k {
      //如果k在以prefix开头的字典个数的范围内，则进入这棵子树
      prefix *= 10
      //1->10,位置移动了一步，所以p也要移动
      p++
    } else if (p + cnt - 1) < k {
      //如果k比这棵子树的范围还要大，那么要增加prefix的大小
      prefix++
      //并且位置p可以直接跨越cnt个
      p += cnt
    }
  }
  return prefix
}
//获得以数字i开头的数字字典个数
func getCount(x, n int) int {
  ans := 0
  start, end := x, x+1
  for start <= n {
    //如果end>n,则要缩小范围，n+1~end都是无效数字
    ans += min(n+1, end) - start
    //[1,2]--->[10,20]
    start *= 10
    end *= 10
  }
  return ans
}
func min(i, j int) int {
  if i < j {
    return i
  }
  return j
}