leetcode 440 字典序的第K小数字
z
 2019-06-30 16:31:32  

给定整数 n 和 k，找到 1 到 n 中字典序第 k 小的数字。注意：1 ≤ k ≤ n ≤ 109。

示例 :

1
2
3
4
5
6
输入:
n: 13   k: 2
输出:
10
解释:
字典序的排列是 [1, 10, 11, 12, 13, 2, 3, 4, 5, 6, 7, 8, 9]，所以第二小的数字是 10。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution(object):
    def findKthNumber(self, n, k):
        """
        :type n: int
        :type k: int
        :rtype: int
        """
        def getSteps(cur1, cur2, n):
            steps = 0
            while cur1 <= n:
                steps += min(n+1, cur2) - cur1
                cur1 *= 10
                cur2 *= 10
            return steps
            
        cur = 1
        k = k-1
        while k > 0:
            steps = getSteps(cur, cur+1, n)
            if k >= steps:
                cur = cur + 1
                k = k - steps
            else:
                cur = cur * 10
                k = k - 1
        return cur