[算法积累] [leetcode] [第k大/字典树] [7] 440.字典序的第k小数字

1.头脑风暴

首先解析题目,第k大元素或者第k小元素的思路应该是:

• 优先级队列
• 快排

字典序，能够想到的是：

• 字典树

其他的头脑风暴:

• 基数排序

这个题目的思路有点像字典树。字典树是每一个节点下面有26个字符。这个题目是每个节点下面有0-9十个节点。是一个抽象的十叉树.

2.思路

由于是字典序,按位比较，前缀小的放在前面。

因此我们其实只需要找到这个第k个元素到底是在哪个子树下面就可以了。

首先，我们需要找到每个子树的数量.只需要减去后一个前缀的第一个就好

long getNum(long prefix,long n){
        long cur = prefix;
        long next = prefix+1;
        long count = 0;
        while(cur <= n){
            count += min(n+1,next) - cur;
            cur *= 10;
            next *= 10;
        }
        return count;
    }

这里我们的cur与next分别指向当前与下一个,之后依次*10,进行下一层.

找到当前子树的个数，我们就可以对1-n进行遍历了.

p表示我们当前访问的下标,prefix指我们在哪个树的子树中,k是第几小

prefix*= 10表示的是再下一层,prefix++,表示的是往右移一位

		long p = 1;
        long prefix = 1;
        while(p < k){
            long num = getNum(prefix,n);
            if(p + num > k){
                prefix *= 10;
                p++;
            }else{
                prefix ++;
                p += num;
            }
        }
        return static_cast<int> (prefix);