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

注意：1 ≤ k ≤ n ≤ 10^9。

示例 :

輸入:
n: 13
k: 2

輸出: 10

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

字典排序數的實現可以參考leetcode-386

字典排序數即10叉樹的形態，數值排列按照 字符串首字母的ascii碼值進行排序
那么數值的字典序即為一個十叉樹，比如以1為樹頂的樹狀形式如下：
1
｜
10 11 … 19
｜\
100 101 102…109

可以看到第一層第一個數 1 和第二層之間的計算方式：
1 *10 + (1…9)
第二層 第一個數 100 和第三層之間的計算方式
10*10 + (1…9)

此時我們要在n (1…10^9)的范圍內找到第k大的數。

如果一個個查找，勢必效率低下。那么可以縮短查找路徑，方式如下：

1. 獲取以1開頭和以2開頭數值之間的 數值個數，和k值比較
   如果大于k,說明在以1開頭之下的某一層中，即可增加層數繼續在下一層10…11之間的數值個數，縮短k的路徑
   如果小于k,那么需要更換子樹，更改為以 2 開頭的字典樹
2. 計算的數值個數需要在n的范圍內，同時每當層數遞增時需縮減k的數值，相當于重新找到了計算起點

實現如下:

/*計算[n,n+1]范圍內滿足小于max的字典數的個數*/
int getCount(long n, int max) {int res = 1;long left = n *10 + 0;//n下一層的第一個數long right = n *10 + 9;//n下一層的第10個數while(left <= max) {if (max <= right) { //max在[n,n+1]之間res += (max - left + 1);} else {res += (right - left + 1);}left = left * 10 + 0;//繼續遞增層數right = right *10 + 9;}return res;
}int findKthNumber(int n, int k) {//return cur;long l = 1;long r = 9;while(k) {for (long i = l;i <= r; ++i) {int f = getCount(i, n);//獲取[i,i+1]之間的字典數的個數，并和k進行比較//發現k大于上一個子樹中字典樹數的數值個數，那么更換子樹iif (f < k) {k -= f;}else {//否則，繼續深度搜索，縮減k的范圍并進入到當前子樹的下一層k --;if(k == 0) return i;l = i *10 + 0;r = i *10 + 9;break;}}}return 0;
}

總結

以上是生活随笔為你收集整理的leetcode-440 字典序的第K小数字的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。