440. The k-th small number of dictionary order (difficult) - dictionary tree - number node - byte skipping high-frequency question

One 、 Title Description

Given integer n and k, return [1, n] Chinese dictionary order No k Small numbers .

Example 1：

 Input : n = 13, k = 2
 Output : 10
 explain :  The order of the dictionary is  [1, 10, 11, 12, 13, 2, 3, 4, 5, 6, 7, 8, 9], So the second smallest number is  10.

Example 2：

 Input : n = 1, k = 1
 Output : 1

Example 3：

 Input ：target = 11, nums = [1,1,1,1,1,1,1,1]
 Output ：0

Two 、 Problem solving

Dictionary tree

First of all, let's look at 386 topic . This question is No k Small numbers , In fact, it is to find the number of child nodes of each node in the tree , Then with K Value is compared with .

Among them, the first node of the first layer 1 Calculation , Look at it 1 Is the number of child nodes below the node . If the number of child nodes of the current node is greater than K, Then the target value is under the subtree , Then look down layer by layer , Update node values ,1->10, It also needs to be updated K value , That is, the first number of the second time 0, Then calculate the 0 How many child node values are there below , Keep on executing , Until the final value is found .
If the first node of the first layer 1 The number of child nodes below the value is less than K value , Description at node 2 Next look , to update K value , Execute sequentially .

If it's under the first node of the first layer , Just look down on each floor in turn ;

class Solution {
    
    public int findKthNumber(int n, int k) {
    
        long cur = 1;
        k--;
        while(k > 0){
    
            int nodes = countNodes(n,cur);
            if(k >= nodes){
    
                k = k - nodes;
                cur++;
            }else{
    
                k--;
                cur *= 10;
            }
        }
        return (int) cur;
    }

    public int countNodes(long n,long cur){
    
        long total = 0;
        long next = cur + 1;
        while(cur <= n){
    
            total += Math.min(n - cur + 1,next -cur);
            cur *= 10;
            next *= 10;
        }
        return (int) total;
    }
}

Output test ：

Code ：

class Solution {
    
    public int findKthNumber(int n, int k) {
    
        long cur = 1;
        k--;
        System.out.println("0->k："+k);
        while(k > 0){
    
            int nodes = countNodes(n,cur);
            System.out.println("nodes："+nodes);
            if(k >= nodes){
    
                k = k - nodes;
                System.out.println("1->k："+k);
                cur++;
                System.out.println("1->cur："+cur);
            }else{
    
                k--;
                System.out.println("2->k："+k);
                cur *= 10;
                System.out.println("2->cur："+cur);
            }
        }
        return (int) cur;
    }

    public int countNodes(long n,long cur){
    
        long total = 0;
        long next = cur + 1;
        while(cur <= n){
    
            // Calculate the number of nodes in each layer , Then count the initial cur Value less than n Of nodes 
            total += Math.min(n - cur + 1,next -cur);
            System.out.println("total："+total);
            cur *= 10;
            next *= 10;
        }
        return (int) total;
    }
}

0->k：65
total：1
total：11
total：35
nodes：35
1->k：30
1->cur：2
total：1
total：11
nodes：11
1->k：19
1->cur：3
total：1
total：11
nodes：11
1->k：8
1->cur：4
total：1
total：11
nodes：11
2->k：7
2->cur：40
total：1
nodes：1
1->k：6
1->cur：41
total：1
nodes：1
1->k：5
1->cur：42
total：1
nodes：1
1->k：4
1->cur：43
total：1
nodes：1
1->k：3
1->cur：44
total：1
nodes：1
1->k：2
1->cur：45
total：1
nodes：1
1->k：1
1->cur：46
total：1
nodes：1
1->k：0
1->cur：47

analysis ： The first node of the first layer 1 The number of child nodes is 35, Less than K value , Then continue on node 2 Search for , to update k The value is 30, And then the nodes 2 The number of child nodes is 11, Less than 30, Then continue on node 3 Search for , And then update K The value is 19, In turn