首页 > 代码库 > [LeetCode] K-th Smallest in Lexicographical Order 字典顺序的第K小数字
[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: 2Output:10Explanation:The lexicographical order is [1, 10, 11, 12, 13, 2, 3, 4, 5, 6, 7, 8, 9], so the second smallest number is 10.
s
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; }};
类似题目：
Lexicographical Numbers
参考资料：
https://discuss.leetcode.com/topic/64624/concise-easy-to-understand-java-5ms-solution-with-explaination/2
https://discuss.leetcode.com/topic/64462/c-python-0ms-o-log-n-2-time-o-1-space-super-easy-solution-with-detailed-explanations
LeetCode All in One 题目讲解汇总(持续更新中...)
[LeetCode] K-th Smallest in Lexicographical Order 字典顺序的第K小数字
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。