[leetcode/lintcode 題解] 阿裡面試真題：字典序的第K小數字

描述

給定整數n和k，找到按字典序排序的第k個最小整數，範圍從1到n。

1 ≤ k ≤ n ≤ 1e9.

線上評測位址：

領扣題庫官網

樣例1
輸入：200,18
輸出：114
解釋：1,10,100,101,102,103,104,105,106,107,108,109,11,110,111,112,113,114，第十八個是114。           

樣例2
輸入：13，2
輸出：10
解釋：按字典序排列順序為 [1, 10, 11, 12, 13, 2, 3, 4, 5, 6, 7, 8, 9], 是以第二小的數字為10。           

考點

• 字元串
• 枚舉

題解

字元串的構造類似于十叉樹，用k減去子節點的個數，step表示以curr開頭至curr+1開頭間的字元串數量，step是否小于等于k，如果是，我們cur自增1，k減去step；如果不是，說明要求的數字在子節點中，我們此時cur乘以10，k自減1，以此類推，直到k為0推出循環，此時cur即為所求。

public class Solution {
    /**
     * @param n: a integer
     * @param k: a integer
     * @return: return a integer
     */
    public int findKthNumber(int n, int k) {
        int curr = 1;
        k = k - 1;
        while (k > 0) {
            int steps = calSteps(n, curr, curr + 1);
            if (steps <= k) {   //如果不在目前層，減去steps
                curr += 1;      
                k -= steps;  
            } 
            else {              //說明在目前層,curr*10縮小搜尋範圍繼續查找
                curr *= 10;
                k -= 1;
            }
        }
        return curr;
    }
    //use long in case of overflow
    public int calSteps(int n, long n1, long n2) { //計算curr開頭和curr+1開頭之間的字元串數量
        int steps = 0;
        while (n1 <= n) {
            steps += Math.min(n + 1, n2) - n1;  //每次加上目前的字元串數量
            n1 *= 10;       //每次均擴大10倍
            n2 *= 10;
        }
        return steps;
    }
}           

更多題解參考：

九章官網solution