[LeetCode] K-th Smallest in Lexicographical Order 字典顺序的第K小数字
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 Numbers的延伸,之前让按字典顺序打印数组,而这道题让我们快速定位某一个位置,那么我们就不能像之前那道题一样,一个一个的遍历,这样无法通过OJ,这也是这道题被定为Hard的原因。那么我们得找出能够快速定位的方法,我们如果仔细观察字典顺序的数组,我们可以发现,其实这是个十叉树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推出循环,此时cur即为所求:
class Solution { public: int findKthNumber(int n, int k) { int cur = 1; --k; while (k > 0) { long long step = 0, first = cur, last = cur + 1; while (first <= n) { step += min((long long)n + 1, last) - first; first *= 10; last *= 10; } if (step <= k) { ++cur; k -= step; } else { cur *= 10; --k; } } return cur; } };
类似题目:
参考资料:
相关文章
- Leetcode 之Populating Next Right Pointers in Each Node II(51)
- Leetcode 之Largest Rectangle in Histogram(40)
- leetcode 之Reverse Nodes in k-Group(22)
- Java实现 LeetCode 792 自定义字符串排序(暴力)
- Java实现 LeetCode 661 图片平滑器(暴力)
- Java实现 LeetCode 622 设计循环队列(暴力大法)
- Java实现 LeetCode 498 对角线遍历
- Java实现 LeetCode 368 最大整除子集
- Java实现 LeetCode 200 岛屿数量
- Java实现 LeetCode 129 求根到叶子节点数字之和
- Java实现 LeetCode 97 交错字符串
- Java实现 LeetCode 92 反转链表 II
- 【贪心】LeetCode 309. 最佳买卖股票时机含冷冻期【中等】
- LeetCode: 106_Construct Binary Tree from Inorder and Postorder Traversal | 根据中序和后序遍历构建二叉树 | Medium
- LeetCode:151_Reverse Words in a String | 字符串中单词的逆反 | Medium
- [LeetCode] Delete Node in a Linked List
- [LeetCode] Reverse Words in a String
- LeetCode-1487. 保证文件名唯一【哈希表,字符串】
- ( “树” 之 DFS) 101. 对称二叉树 ——【Leetcode每日一题】
- LeetCode - 354 俄罗斯套娃信封问题
- LeetCode - 93 复原 IP 地址
- Find Minimum in Rotated Sorted Array 旋转数组中找最小值 @LeetCode
- Leetcode 2016. 增量元素之间的最大差值(暴力枚举方法)
- Leetcode 1598. 文件夹操作日志搜集器
- Leetcode 504. 七进制数
- [LeetCode] Search in Rotated Sorted Array II [36]
- LeetCode 154 Find Minimum in Rotated Sorted Array II
- [LeetCode] Delete Node in a Linked List
- leetcode 720. Longest Word in Dictionary
- leetcode 501. Find Mode in Binary Search Tree
- leetcode 783. Minimum Distance Between BST Nodes 以及同样的题目 530. Minimum Absolute Difference in BST
- leetcode 637. Average of Levels in Binary Tree
- 【Mac系统】Vscode使用LeetCode插件报错‘leetcode.toggleLeetCodeCn‘ not found