LeetCode# dictionary sequence of the first 440 k small digital clock | brush

input

• N: Number size
• K: the KTH smallest number

example

Input: (13,2) output: 10 Reason: [1, 10, 11, 12, 13,2, 3, 4, 5, 6, 7, 8, 9], 10 is the second smallest number

Train of thought

• To understand the lexicographical order of numbers, you can think of it as a decadic tree with roots of 1 and children of 10-19, roots of 2 and children of 20-29
• Enter k, which is understood as the number of steps to take in the array
• Define 5 variables, result = 1 final result; LastSteps = k-1 indicates the number of remaining steps; Left = result left; Right = result+1; Count = 0 Records the number of nodes to be crossed
• So let’s look for the range that we end up in, that is, who is the root of the dissatisfied tree
• When left <= n, prove that the final position is to the right or below the current node
• If right is less than n+1, count += min(right, n+1) -left
• Compare the accumulated nodes with the current number of remaining steps until left is greater than n
• If lastSteps > count, verify that all children of the left node are completed, so you need to go one step to the right. result += 1;
• If lastSteps <= count, the left child is sufficient to complete the remaining steps, then go down one step, lastSteps–; result*=10;
• When the number of remaining steps is 0, result is the final result

code

class Solution {
    public void int findKthNumber(int n, int k) {
        int result = 1;
        int lastSteps = k - 1; // The default step is to go to the first number
        while (lastSteps > 0) {
            long left = result; // Use long to prevent left * 10 from overrunning when n reaches near 2 ^ 32
            long right = result + 1;
            int count = 0;
            while(left <= n) { // Explore down or to the right to count the number of nodes to cross
                count += Math.min(right, n+1) - left;
                left *= 10;
                right *= 10;
            }
            
            if (count > lastSteps) { // There are too many nodes to cross, you can only go down one layer
                lastSteps --;
                result *= 10;
            } else { // If there are not enough nodes, the current number of steps is enough to go to the entire node, directly over the node and its children, one step to the rightlastSteps -= count; result ++; }}returnresult; }}Copy the code