Leetcode0440. 字典序的第K小数字(difficult，三种算法)

目录

1. 题目描述

2. 解题分析

2.1 作弊的解法

2.2 哈希 减而治之

2.3 字典树

3. 代码实现

---

1. 题目描述

给定整数 n 和 k，返回 [1, n] 中字典序第 k 小的数字。

示例 1:

输入: n = 13, k = 2
输出: 10
解释: 字典序的排列是 [1, 10, 11, 12, 13, 2, 3, 4, 5, 6, 7, 8, 9]，所以第二小的数字是 10。

示例 2:

输入: n = 1, k = 1
输出: 1

提示:

• 1 <= k <= n <= 10^9

2. 解题分析

2.1 作弊的解法

        利用Python的强大的内置字符串处理能力，这个问题的解决极其简单。

        Python提供了内置的字符串排序方法，对字符串排序就是按字典序排序。

        先将数字转换为字符串，然后按照字符串排序，最后在取字典序排序的第k个转换回数字即可。

        但是，这种方法因为需要将所有的数先变换成字符串然后再一起进行排序处理，仅限于数据量比较小时可用。题设要求n最大可达10**9，首先内存需求就非常大，字符串排序也非常耗时，无法满足leetcode的复杂度评估要求。但是这个实现可以作为一个参考，代码参见以下findKthNumber1()。

2.2 哈希 减而治之

        按字典序排序，就是首先看各数的最高位，如果最高位相同，则看次高位，。。。，然后依此类推。

        所以考虑这样一个基本的思路：按照目标数的最高位、次高位。。。的顺序逐步确定。

        首先建立一个哈希表。以数的最高位为key，最高位为该key的数的列表作为value。

        这个表就代表了对原数组的一个按字典序分区间排序。每区间之内的数暂时还不是按字典序排列的。基于这个表中各区间的元素个数，并与k做对比，很容易确定目标数应该处于哪个区间。

        然后，针对该区间的数重新进行以上处理，这样逐步缩小范围最终就可以找到目标数。

        代码参见以下 findKthNumber2().

        满以为这个操作很秀。。。然而，这个算法得速度居然比上一个解法还要慢，很受伤^-^

2.3 字典树

        对于这个搜索的结构隐约有点想法，但是。。。嗯，不打算再死磕了。偷窥了一下官解，字典树！原来如此。没有学习过字典树（惭愧，不过这下就算学习过了），难怪想不到。。。（给我足够多的时间去死磕，是不是也能重新“发明”出字典树这种数据结构来呢？回过头来看，其实解法2已经孕育了字典树的雏形了😂）

        利用字典树的特性将所有小于等于 n 的数字按照字典序的方式进行重建，可以构建字典树如下（以1为根节点，然后每个节点i的子节点为 (10*i, 10*i 1, ..., 10 *i 9)），这个可以看作是一个10叉树：

         通过观察可以发现，前序遍历该字典树即可得到字典序从小到大的数字序列，遍历到第 k 个节点即为按字典序第 k 小的数字。我们可以构造字典树，并通过前序遍历求得目标节点，时间复杂度为 O(k)。

        但是，构建字典树本身是一个很大的工程，能不能省掉这个显式地构建字典树及其遍历过程呢？

        考虑当前字典树的第 i (i<k)小的节点为，则只需要从节点i开始再按前序遍历往后找(k-i)个节点即可。记以节点为根节点的子树的节点数为，分以下几种情况讨论：

1. 如果< k-i，则目标节点不在该子树中，可以跳过该子树的搜索，而是从字典序下一个节点开始找个节点即可
2. 如果>= k-i，则目标节点在该子树中，则可以从 节点 的子树中去寻找。 比如说，接下来可以从节点 的最左边子节点（为）开始寻找个节点即可。
3. 重复以上过程即可

        以上显然形成了规整的问题-子问题的分解结构，适合于基于递归方式的动态规划方法来解决。

        以上还有一个遗留问题，即确定节点为根节点的子树的节点数。这个可以利用层序遍历的方式来求解。 从节点x开始，它的子节点为{10x, 10x 1, ..., 10x 9}，然后再分别按照这个规则进行展开到下一层子节点，直到n为止。

        以上这样的算法处理相比于显式地构建并遍历字典树的方式的优势在于，对子树的求解是按需的，即只是根据需要进行子树的计求解算，而不像构建字典树一样一上来不管三七二十一先把整个字典树构建出来。而且，不管k多大，其所需要处理的时间步数差别不大（某种意义上可以与十分法搜索相类比！）。而真正的字典树遍历则k越大所需要遍历的步数就越大。 

        代码参见以下 findKthNumber3().

        不过令人惭愧的是，我做出来的基于字典树的实现居然比findKthNumber1()，直叫人想找块豆腐把自己撞死算了。。。

        无力再战了，回头再来运行速度如此之慢的原因。

3. 代码实现

1.  
   class Solution:
2.  
    
3.  
   def findKthNumber1(self, n: int, k: int) -> int:
4.  
   numstr = [str(k 1) for k in range(n)]
5.  
   numstr.sort()
6.  
   # print(numstr)
7.  
   nums = [int(numstr[k]) for k in range(n)]
8.  
   return nums[k-1]
9.  
    
10.  
    def findKthNumber2(self, n: int, k: int) -> int:
11.  
     
12.  
    nums = [j 1 for j in range(n)]
13.  
    round = 0
14.  
    while len(nums)>1:
15.  
    # print(round,nums)
16.  
    # if max(nums) < 10:
17.  
    # return nums[k-1]
18.  
     
19.  
    # Create the hash table
20.  
    d = dict()
21.  
    for j in range(10):
22.  
    d[j] = []
23.  
    for m in range(len(nums)):
24.  
    mStr = str(nums[m])
25.  
    if len(mStr) > round:
26.  
    d[int(mStr[round])].append(nums[m])
27.  
    else:
28.  
    # d[0].append(m)
29.  
    k -= 1
30.  
    if k<=0:
31.  
    return nums[m]
32.  
    # print(round,k,nums,d)
33.  
    # Serach for the period in which the target can be found
34.  
    cnt = 0
35.  
    for j in range(10):
36.  
    cnt_prev = cnt
37.  
    cnt = len(d[j])
38.  
    if cnt >= k:
39.  
    nums = d[j]
40.  
    k -= cnt_prev
41.  
    break
42.  
    round = 1
43.  
    # if round > 10: # temporarily for debug
44.  
    # break
45.  
    return nums[0]
46.  
     
47.  
    def findKthNumber3(self, n: int, k: int) -> int:
48.  
     
49.  
    def subTreeSize(i):
50.  
    # print('subTreeSize(): ',i)
51.  
    if i>n:
52.  
    return 0
53.  
    cnt = 1
54.  
    for node in range(10*i,10*i 10):
55.  
    cnt = cnt subTreeSize(node)
56.  
    return cnt
57.  
     
58.  
    def dp(i, k):
59.  
    # print('dp:',i,k)
60.  
    # baseline case
61.  
    if k==1:
62.  
    return i
63.  
    k = k-1
64.  
    for m in range(10):
65.  
    x = 10*i m
66.  
    if x==0:
67.  
    continue
68.  
    size_x = subTreeSize(x)
69.  
    # print('subTreeSize: ',x,size_x)
70.  
    if size_x >= k:
71.  
    return dp(x,k)
72.  
    else:
73.  
    k = k - size_x
74.  
     
75.  
    return dp(0,k 1)

回到主目录：笨牛慢耕的Leetcode解题笔记(动态更新。。。)https://chenxiaoyuan.blog.csdn.net/article/details/123040889

这篇好文章是转载于：学新通技术网