## 题目描述：

LeetCode 440. K-th Smallest in Lexicographical Order

Given integers `n` and `k`, find the lexicographically k-th smallest integer in the range from `1` to `n`.

Note: 1 ≤ k ≤ n ≤ 109.

Example:

```Input:
n: 13   k: 2

Output:
10

Explanation:
The lexicographical order is [1, 10, 11, 12, 13, 2, 3, 4, 5, 6, 7, 8, 9], so the second smallest number is 10.
```

## 解题思路：

```p        q         gap
3        4         1
30       40        11
300      400       111
3000     4000      1111
30000    40000     6881```

## Python代码：

``````class Solution(object):
def findKthNumber(self, n, k):
"""
:type n: int
:type k: int
:rtype: int
"""
ans = 1
k -= 1
while k > 0:
gap = self.findGap(n, ans, ans + 1)
if gap <= k:
ans += 1
k -= gap
else:
ans *= 10
k -= 1
return ans

def findGap(self, n, p, q):
gap = 0
while p <= n:
gap += max(0, min(n + 1, q) - p)
p *= 10
q *= 10
return gap
``````

## Python代码：

``````class Solution(object):
def findKthNumber(self, n, k):
"""
:type n: int
:type k: int
:rtype: int
"""
if n < 10: return k
sn = str(n)
po = int('1' * len(sn))
fd = int(sn[0])
lo = (fd - 1) * po
mi = lo + self.calcMi(n)
hi = lo + self.calcHi(n)
if k > hi:
po /= 10
k -= hi
fc = (k - 1) / po + fd + 1
k += fd * po
elif k > mi:
return self.solveMi(9 * po / 10, n / 10 + 1, k - mi - 1)
else:
fc = (k - 1) / po + 1
return int(str(fc) + self.solve(9 * po / 10, k - (fc - 1) * po - 1))

def calcMi(self, n):
res = 1
mask = 10 ** int(math.log(n, 10))
while n > 9:
res += 1 + n % mask
n /= 10
return res

def calcHi(self, n):
res = 1 + int('1' * (len(str(n)) - 1))
mask = 10 ** int(math.log(n, 10))
return res + n % mask

def solve(self, n, k):
if k == 0: return ''
if n <= 10: return str(k - 1)
po = int('1' * len(str(n)))
fc = (k - 1) / po
rest = self.solve(9 * po / 10, k - fc * po - 1)
return str(fc) + rest

def solveMi(self, n, k, r):
if r <= n - k: return k + r
return self.solveMi(n / 10, k / 10 + 1, r - n + k)
``````

Pingbacks已关闭。

1. 唐小牛 发布于 2016年11月25日 07:57 #

请问第一种解法，gap是怎么算出来的。

2. 在线疯狂 发布于 2016年11月25日 12:15 #

利用findGap函数，我在博文里补充了一个例子，不知能否帮助理解。