Trie
Description
Given two integers n
and k
, return the kth
lexicographically smallest integer in the range [1, n]
.
Example 1:
Input: n = 13, k = 2
Output: 10
Explanation: The lexicographical order is [1, 10, 11, 12, 13, 2, 3, 4, 5, 6, 7, 8, 9], so the second smallest number is 10.
Example 2:
Input: n = 1, k = 1
Output: 1
Constraints:
Solutions
Solution 1
Python3 Java C++ Go
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20 class Solution :
def findKthNumber ( self , n : int , k : int ) -> int :
def count ( curr ):
next , cnt = curr + 1 , 0
while curr <= n :
cnt += min ( n - curr + 1 , next - curr )
next , curr = next * 10 , curr * 10
return cnt
curr = 1
k -= 1
while k :
cnt = count ( curr )
if k >= cnt :
k -= cnt
curr += 1
else :
k -= 1
curr *= 10
return curr
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31 class Solution {
private int n ;
public int findKthNumber ( int n , int k ) {
this . n = n ;
long curr = 1 ;
-- k ;
while ( k > 0 ) {
int cnt = count ( curr );
if ( k >= cnt ) {
k -= cnt ;
++ curr ;
} else {
-- k ;
curr *= 10 ;
}
}
return ( int ) curr ;
}
public int count ( long curr ) {
long next = curr + 1 ;
long cnt = 0 ;
while ( curr <= n ) {
cnt += Math . min ( n - curr + 1 , next - curr );
next *= 10 ;
curr *= 10 ;
}
return ( int ) cnt ;
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32 class Solution {
public :
int n ;
int findKthNumber ( int n , int k ) {
this -> n = n ;
-- k ;
long long curr = 1 ;
while ( k ) {
int cnt = count ( curr );
if ( k >= cnt ) {
k -= cnt ;
++ curr ;
} else {
-- k ;
curr *= 10 ;
}
}
return ( int ) curr ;
}
int count ( long long curr ) {
long long next = curr + 1 ;
int cnt = 0 ;
while ( curr <= n ) {
cnt += min ( n - curr + 1 , next - curr );
next *= 10 ;
curr *= 10 ;
}
return cnt ;
}
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25 func findKthNumber ( n int , k int ) int {
count := func ( curr int ) int {
next := curr + 1
cnt := 0
for curr <= n {
cnt += min ( n - curr + 1 , next - curr )
next *= 10
curr *= 10
}
return cnt
}
curr := 1
k --
for k > 0 {
cnt := count ( curr )
if k >= cnt {
k -= cnt
curr ++
} else {
k --
curr *= 10
}
}
return curr
}
GitHub