[LeetCode]K-th Smallest in Lexicographical Order

题目描述:

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.

题目大意:

给定整数n和k,计算从1到n的整数中字典序第k小的数。

注意: 1 ≤ k ≤ n ≤ 109

解题思路:

解法I 直接构造法

初始令答案ans = 1,当k值>0时执行循环:

计算ans与ans + 1之间的数字个数gap

若gap <= k:则令ans = ans + 1,k = k - gap

否则令ans = ans * 10,k = k - 1

当n, p, q = 35769, 3, 4时,findGap函数执行过程如下:

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

解法II 将整数1到n划分为3个区间分别求解

区间1:字典序 ≤ n

区间2:首位数 = n的首位数,且字典序 > n

区间3:首位数 > n

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
            mask /= 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)

 

本文链接:http://bookshadow.com/weblog/2016/10/24/leetcode-k-th-smallest-in-lexicographical-order/
请尊重作者的劳动成果,转载请注明出处!书影博客保留对文章的所有权利。

如果您喜欢这篇博文,欢迎您捐赠书影博客: ,查看支付宝二维码

Pingbacks已关闭。

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

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

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

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

张贴您的评论