首页 > itarticle > 笔试题整理

笔试题整理

admin 11月 12, 2020 0

笔试题整理

LeetCode 440 K-th Smallest in Lexicographical Order

hulu笔试的第二题。

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

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

class  
{
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;