每日一题-字典序的第K小数字

440. 字典序的第K小数字

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/k-th-smallest-in-lexicographical-order

题目

给定整数 n 和 k，返回 [1, n] 中字典序第 k 小的数字。

思路

同层从左到右字典序以此增大，字典序处于同层两个节点间的有$x$个，$x$取决于当前层高和节点总数$n$。如果$k$剩余大于等于两个节点间所有节点，则向右移动同时减去相应节点数，否则向下移动。

代码

class Solution {
	public:
	    int count(long long n, long long cur) {
		// 计算同层两个节点间字典数
		long long next = cur+1;
		long nodes = 0;
		while(cur <= n) {
			nodes += min(n-cur+1, next-cur);
			cur *= 10;
			next *= 10;
		}
		return nodes;
	}
	int findKthNumber(int n, int k) {
		int cur = 1;
		--k;
		while(k) {
			// k为0时当前节点就是答案
			int nodes = count(n,cur);
			if (k >= nodes) {
				// 向右走 减去中间差
				k -= nodes;
				++cur;
			} else {
				// 向下走 注意只跳过了cur这个节点
				--k;
				cur *= 10;
			}
		}
		return cur;
	}
}
;