The title

Given integers n and k, return the lexicographical KTH smallest number in [1, n].

Example 1

Input: n = 13, k = 2 Output: 10 Explanation: The lexicographical order is [1, 10, 11, 12, 13, 2, 3, 4, 5, 6, 7, 8, 9], so the second smallest number is 10.Copy the code

Example 2

Input: n = 1, k = 1 Output: 1Copy the code

prompt

  • 1 <= k <= n <= 109

Answer key

The simpler the problem, the bigger the problem, that’s it; The topic a word, the solution to the problem to think for a long time.

Multi-fork tree forward traversal

graph TD root --> 1 root --> 2 root --> 3[...]  root --> 9 1 --> 10 1 --> 11 1 --> 12[...] 1 --> 19 10 --> 100 10 --> 101 10 --> 102[... 10 -- - > 109
  • The lexicographical order from 1 to n can be regarded as the nodes of the incomplete 9-tree mentioned above;
  • The KTH node traversed from the preceding node of the 9-tree is the KTH smallest of the lexicographical order

The above graphics have given the solution idea, the following is to convert the idea into code

  • Can we just build a 9-fork tree from 1 to n? It could be, but the complexity is a little bit high, so you just need to find the KTH tree and build the whole tree, which is not worth the loss
  • The tree can be used to simulate the preorder traversal and reduce the time complexity

How to simulate?

  • If we now have a method called getChildren, we can get how many children are under the current node.

    • Let’s say 1 to 100,1 has 12 nodes under it

  • Suppose the number of children is less than k

    • Note The current node contains all its children is not the answer. The answer is in the other siblings of the current node.
    • K minus child; And check whether the number of child nodes is less than k-child in sibling nodes of the current node
    • Repeat the above steps

  • If number of child nodes child >= k

    • The answer must exist in the current node or its children
    • Recursively find the relationship between the number of children and k-1
    • Repeat the above steps

    Edit the code as follows:

    The complete code

var findKthNumber = function (n, k) {
  let count = 1;
  k--;
  while (k > 0) {
    const children = getChildren(count);
    if (children <= k) {
      k -= children;
      count++;
    } else {
      count = count * 10; k--; }}return count;
  function getChildren(c) {
    let child = 0;
    let left = c;
    let right = c;
    while (left <= n) {
      child += Math.min(right, n) - left + 1;
      left *= 10;
      right = right * 10 + 9;
    }
    returnchild; }};Copy the code

conclusion

The author level is limited, if there is insufficient welcome to correct; Any comments and suggestions are welcome in the comments section