笔试题整理

Posted on Edited on In

笔试题整理

[LeetCode 440 K-th Smallest in Lexicographical Order](440 K-th Smallest in Lexicographical Order)

hulu笔试的第二题。

题意是一共n个数，按照字典序排序，问第k个数字是多少。

按照字典序排序之后，会发现是一颗10叉树，在树上不停地往下搜。复杂度$O(log^2n)$

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
class Solution 
{
public:
	int findKthNumber(int n, int k) 
	{
		int ans = 1;
		for (k--; k > 0;)
		{
			long long count = 0;
			for (long long first = ans, second = ans + 1; first <= n; first *= 10,second *= 10)
			{
				count += min(1LL*n + 1, second) - first;
			}
			if (count <= k)
			{
				k -= count;
				ans += 1;
			}
			else
			{
				k--;
				ans *= 10;
			}
		}
		return ans;
	}
}wc;