440. K-th Smallest in Lexicographical Order

Posted on | In

440. K-th Smallest in Lexicographical Order

Description:

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.

解答

这道题一上来可能没思路，仔细想一下发现lexicographical order可以转化为树的先序遍历来做。
具体转化过程如下:

树结构

求第k小的数即是求树的先序遍历的第k个节点的值，我们可以直接构建一个树，但是这样太麻烦。

我们的目标是从第1个节点开始，移动k - 1 步到目标节点。

为了减少移动次数，我们先计算同一level的邻居节点之间的步数以跳过不必要的先序遍历。
比如说假设n为20，k为12，我们一开始处于节点1，我们先计算节点1和2之间的步数（1和2之间有11步），然后令k = k - 11就可以直接跳到节点2，此时k为1，输出节点2的值。

所以总体思路是：假设我们处于cur节点上，我们先计算同一level的邻居节点之间的步数steps，如果steps小于k，我们跳到邻居节点cur + 1，然后令k -= steps,当steps大于等于k时，我们进入树的下一层，然后用同样的方法计算，最终到达目标节点。

那么我们如何计算节点之间的步数呢，假设第一个节点是now，邻居节点是next,当next <= n时，我们就把同一level从now 到next之间的节点数量加上来，如果 next > n，我们就把now到n（包括n）之间的节点数量加上来，然后进入树的下一层重复刚刚的操作。

代码

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
27
28
29
30
31
32
33
34

class Solution {
public:
    long findKthNumber(int n, int k) {
        long cur = 1;
        
        while (k > 1) {
            long steps = calcSteps(cur, cur + 1, n);
            if (steps < k) {
                cur += 1;
                k -= steps;
            }
            else {
                k -= 1;
                cur *= 10;
            }

        }
        return cur;

    }

    long calcSteps(long now, long next, long n) {
        long steps = 0;
        while (now <= n) {

            steps += min(n + 1, next) - now;
            next *= 10;
            now *= 10;

        }
        return steps;
    }
};