字典序第k小的数字

给定整数 n 和 k，找到 1 到 n 中字典序第 k 小的数字。

注意：1 ≤ k ≤ n ≤ 10⁹。

示例 :

输入:

n: 13 k: 2

输出:

解释:

字典序的排列是 [1, 10, 11, 12, 13, 2, 3, 4, 5, 6, 7, 8, 9]，所以第二小的数字是 10。

思路

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

 public 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 step;

     }

 }

巴特西

Leetcode 440.字典序第k小的数字

字典序第k小的数字

思路

最新文章

热门文章