README
¶
字典序的第K小数字
我们如果仔细观察字典顺序的数组，我们可以发现，其实这是个十叉树 Denary Tree，就是每个节点的子节点可以有十个，比如数字 1 的子节点就是 10 到 19，数字 10 的子节点可以是 100 到 109 ，但是由于
n大小的限制，构成的并不是一个满十叉树。
我们分析题目中给的例子可以知道，数字 1 的子节点有 4 个(10,11,12,13)，而后面的数字 2 到 9 都没有子节点，那么这道题实际上就变成了一个先序遍历十叉树的问题，那么难点就变成了如何计算出每个节点的子节点的个数，我们不停的用k减去子节点的个数，当k减到 0 的时候，当前位置的数字即为所求。
现在我们来看如何求子节点个数，比如数字 1 和数字 2，我们要求按字典遍历顺序从 1 到 2 需要经过多少个数字，首先把 1 本身这一个数字加到 step 中，然后我们把范围扩大十倍，范围变成 10 到 20 之前，但是由于我们要考虑n的大小，由于n为 13，所以只有 4 个子节点，这样我们就知道从数字 1 遍历到数字 2 需要经过 5 个数字，然后我们看step是否小于等于k，如果是，我们 cur 自增 1，k减去step；如果不是，说明要求的数字在子节点中，我们此时 cur 乘以 10，k自减 1，以此类推，直到k为 0 推出循环。
[LeetCode] K-th Smallest in Lexicographical Order 字典顺序的第K小数字
Documentation
¶
Overview ¶
* @lc app=leetcode id=440 lang=golang * * [440] K-th Smallest in Lexicographical Order * * https://leetcode.com/problems/k-th-smallest-in-lexicographical-order/description/ * * algorithms * Hard (27.84%) * Likes: 270 * Dislikes: 45 * Total Accepted: 10.9K * Total Submissions: 39.1K * Testcase Example: '13\n2' * * Given integers n and k, find the lexicographically k-th smallest integer in * the range from 1 to n. * * Note: 1 ≤ k ≤ n ≤ 10^9. * * 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. * * *
Source Files