440. K-th Smallest in Lexicographical Order

440. K-th Smallest in Lexicographical Order

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.

思路： 比如10 ~ 20在这一层有10个数，如果20小于n，那么再找第三层100 ~ 200，每层step就min(n + 1, n2) - n1。

class Solution { public int findKthNumber(int n, int k) { int cur = 1; int step; k--; while (k > 0) { step = calStep(n, cur, cur + 1); if (step <= k) { k -= step; cur++; } else { k--; cur *= 10; } } return cur; } private int calStep(int n, long n1, long n2) { int step = 0; while (n1 <= n) { step += Math.min(n + 1, n2) - n1; n1 *= 10; n2 *= 10; } return

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。