440. K-th Smallest in Lexicographical Order 发表于 2022-01-29 123456789101112131415161718192021222324252627282930313233343536class Solution { public int findKthNumber(int n, int k) { int nth = 1; // 当前所在的节点是第 n 大的节点 int prefix = 1; while (nth < k) { int nodeCount = getNodeCount(prefix, n); // 此处统计的节点数量包含当前节点 if (k > nth + nodeCount - 1) { // 要寻找的数在右边的树中 prefix++; nth += nodeCount; // 跳过当前子树 } else { // 要寻找的数在当前子树中 prefix *= 10; nth++; // 当前节点移动至左下角节点,所以 nth++ } } // 跳出时 nth = k, 即找到第 k 小的数 return prefix; } private int getNodeCount(int rootPrefix, int n) { int count = 0; long endPrefix = rootPrefix + 1; // exclusive long prefix = rootPrefix; while (prefix <= n) { count += Math.min(endPrefix, n + 1) - prefix; // n is inclusive, so use n + 1 prefix *= 10; endPrefix *= 10; } return count; }} 注意在计算节点数量过程中的数据越界问题,题目输入的数据最高为九次方。 Reference440. K-th Smallest in Lexicographical Order