First of all, this is definitely not clickbait, and I promise it’s hard stuff. Maybe someone will think very very hard very strange, but I want to say is that for technical community, the study of the theory of system knowledge has its own place, I think the community should inject some new blood, to share some information content, rather than turned and tossed reorganize clearly has very good knowledge “Fried rice” now to occupy the community the latest articles section.

All right, let’s finish with “B”. Now get down to business.

Let’s begin with the title:

Excerpt from leetcode, I just bought VIP recently, so I can see the frequency of the questions 🙂

What is lexicographical order? How do I locate this number? Yes, when I first came into contact with this topic, my mind was also in a mess.

But I think the most important skill for an intelligent programmer is the ability to quickly abstract and disassemble a problem. After a period of reflection, I still have no answer in my head.

Ha ha.

Without further ado, let’s analyze the problem.

First of all, what is lexicographical order?

What is lexicographical order?

In short, sort the numbers by their prefix,

For example, 10 is less than 9, because 10 is prefixed with 1, which is less than 9,

Or 112 is less than 12, because the prefix 11 is less than 12.

When you sort this way, it’s going to be very different from the usual ascending sort. Just to give you an intuition, multiply a number by 10, or add 1, which is bigger? You might be surprised to find that the latter is even bigger.

But when you get to the bottom of it, you won’t be surprised at all.

Problems in modeling

Let me draw a picture of it.

Each node has 10 child nodes because, as a prefix, it can be followed by 10 numbers from 0 to 9. And you can very easily see that lexicographical ordering is just a preemptive traversal of the tree. 1, 10, 100, 101… 11, 110…

So back to the idea, we need to find the KTH digit. To find out where he ranks, you need to know three things:

  1. How do I determine the number of children under a prefix?
  2. If the KTH number is under the current prefix, how do I go down to the child node?
  3. If the KTH number is not the current prefix, that is, the current prefix is small, how to expand the prefix and increase the search scope?

Next, let’s take these questions apart.

Straighten out the train of thought

1. Determine the number of children under the specified prefix

The task now is to return the total number of next face nodes given a prefix.

The idea here is to subtract the starting point of the next prefix from the starting point of the current prefix, so that is the sum of all the children under the current prefix.

//prefix is a prefix and n is an upper bound
var getCount = (prefix, n) = > {
    let cur = prefix;
    let next = prefix + 1;// Next prefix
    let count = 0;
    // The current prefix must not be greater than the upper bound
    while(cur <= n) {
        count += next - cur;// Start of the next prefix minus the start of the current prefix
        cur *= 10; 
        next *= 10;
        // If prefix was 1 and next was 2, now it's 10 and 20, respectively
        // The number of children prefixed by 1 is increased by 10
        
        // If prefix is 10 and next is 20, then it is 100 and 200 respectively.
        // Add 100 child nodes prefixed by 1, adding one more layer to the tree
    }
    return count;// Return the child node and under the current prefix.
}
Copy the code

Of course, I don’t know if you noticed the problem, but when next is greater than the upper bound, then the dectree with this prefix as the root node is not a full dectree, it should go to the upper bound, there are no children after it. Count += next – cur

count += Math.min(n+1, next) - cur;
Copy the code

You may ask: Huh? Why is it n plus 1 instead of n? What happened to n being upper bound?

Let me give you an example, if the upper bound n is now 12, and you figure out the number of children prefixed by 1, first 1 is itself a node, and then you have 10,11,12, so there are four children.

So what if math.min (n, next) -cur?

So that’s one less, 12 minus 10 plus the root, and you end up with three. So we have to write n plus 1.

Now, we have solved the problem of the number of children of prefixes.

2. The KTH number is under the current prefix

Now all YOU have to do is look inside the subtree.

Prefix will do.

prefix *= 10
Copy the code

3. The KTH number is not under the current prefix

To put it bluntly, the current prefix is small, so let’s expand the prefix.

prefix ++;
Copy the code

Frame structures,

So let’s put that together.

let findKthNumber = function(n, k) {
  let p = 1;// as a pointer to the current position, when p==k, that is, the number to rank k
  let prefix = 1;/ / prefix
  while(p < k) {
    let count = getCount(prefix, n);// Get the sum of all children under the current prefix
    if(p + count > k) { // The KTH number is under the current prefix
      prefix *= 10;
      p++; // Set the pointer to the position of the first child, e.g. 11 times 10 becomes 110, and the pointer from 11 points to 110
    } else if(p + count <= k) { // The KTH number is not under the current prefix
      prefix ++;
      p += count;// Note that the pointer points to the start of the next prefix}}return prefix;
};
Copy the code

Complete code presentation

/** * @param {number} n * @param {number} k * @return {number} */
var findKthNumber = function(n, k) {
  let getCount = (prefix, n) = > {
    let count =  0;
    for(let cur = prefix, next = prefix + 1; cur <= n; cur *= 10, next *= 10) 
      count += Math.min(next, n+1) - cur;
    return count;
  }
  let p = 1;
  let prefix = 1;
  while(p < k) {
    let count = getCount(prefix, n);
    if(p + count > k) {
      prefix *= 10;
      p++;
    } else if(p + count <= k) { prefix ++; p += count; }}return prefix;
};
Copy the code

AC successfully!