[LeetCode]K-th Smallest in Lexicographical Order

乍看之下很像寻找array中第k大的数，这样我们用quick select的方法可以达到O(n)的时间复杂度。但是这道题显然还有更效率的办法，参考这篇文章我们可以发现这就是一个denary tree，寻找第字典序第k大的数，就是preorder traversal的第k个节点，但是显然我们不需要O(k)的时间，我们在每一层算出答案应该在哪个节点的子树当中，我们去子树继续寻找。比如对于[1, 233]的区间，我们寻找字典序第123大的数：

• 我们首先算以1为根的子树的大小，其大小为111（1, 10->19, 100->199），说明我们可以直接跳过1
• 继续计算2位根的子树大小，大小为45（2，20->29，200->233），说明答案在以2位根子树当中，我们去子树中继续搜寻第123 - 111 = 12大的数
• 同理我们跳过10位根的子树，因为其size为11（10，100-109）
• 我们到了12后发现要找第一大的数，那么也就是12，return 结果

时间复杂度O(d)，d为10十进制下的位数，所以我们也可以表示成O(log10(n)) = O(log n)，代码如下：

	class Solution {
	public:
	int findKthNumber(int n, int k) {
	int curr = 1, i = 1;
	while(i < k)
	{
	int steps = calSteps(curr, curr + 1, n);
	if(steps <= k - i)
	{
	++curr;
	i += steps;
	}
	else
	{
	curr = curr * 10;
	++i;
	}
	}
	return curr;
	}
	private:
	int calSteps(long lo, long hi, long n)
	{
	int steps = 0;
	while(lo <= n)
	{
	steps += min(hi, n + 1) - lo;
	lo *= 10;
	hi *= 10;
	}
	return steps;
	}
	};

view raw K-th Smallest in Lexicographical Order.cpp hosted with ❤ by GitHub