Leetcode(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:

1
2
3
4
5
6
7
8
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.

解法

思路是：对于每个点，有向右和像下两种走法，如果我们计算这个点一下的节点个数（不包含自己，但包含到这个点右边的节点的个数，在代码里为calstep的返回值），如果比剩余的步数少，则直接向右走，否则向下走。

计算这个点下的数目时，考虑是否为完整层，所以出现了calstep中与n的比较情况

参考思路：https://massivealgorithms.blogspot.com/2016/10/leetcode-440-k-th-smallest-in.html

具体代码如下：

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
class Solution {
    public int findKthNumber(int n, int k) {
        int current = 1;
        k -= 1;
        while (k > 0) {
            long step = calstep(current, current + 1, n);
            if (step <= k) {
                k -= step;
                current = current + 1;
            } else {
                k -= 1;
                current = current * 10;
            }
        }
        return current;
    }

    long calstep(long current, long levelMaxNumber, int n) {
        long step = 0;
        while (current <= n) {
            if (levelMaxNumber > n) {
                step += (n - current + 1);
            } else {
                step += (levelMaxNumber - current);
            }
            current *= 10;
            levelMaxNumber *= 10;
        }
        return step;
    }
}