題目:
給定整數 n 和 k,找到 1 到 n 中字典序第 k 小的數字。
註意:1 ≤ k ≤ n ≤ 109。
示例 :
輸入:
n: 13 k: 2
輸出:
10
解釋:
字典序的排列是 [1, 10, 11, 12, 13, 2, 3, 4, 5, 6, 7, 8, 9],所以第二小的數字是 10。
方法
思路
1、確定壹個前綴下所有子節點的個數
2、如果第 k 個數在當前的前綴下,繼續往下面的子節點找
3、如果第 k 個數不在當前的前綴,即當前的前綴比較小,如何擴大前綴,增大尋找的範圍
時間復雜度:O(n)
空間復雜度:O(1)