當前位置:成語大全網 - 新華字典 - (數組) LeetCode386. 字典序排數

(數組) LeetCode386. 字典序排數

題目:

給定整數 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)