leetcode 链接：440. 字典序的第K小数字

题目

给定整数 n 和 k，找到 1 到 n 中字典序第 k 小的数字。

注意：1 ≤ k ≤ n ≤ 。

示例：

输入:
n: 13   k: 2
输出:
10
解释:
字典序的排列是 [1, 10, 11, 12, 13, 2, 3, 4, 5, 6, 7, 8, 9]，所以第二小的数字是 10。

解答 & 代码

解法一：快速选择 + string 直接比较（超时）

比较的时候将两个数字转换为 string 再直接比较，比较的就是字典序，eg.
to_string(nums[right]) >= to_string(pivot)

class Solution {
private:
    int partition(vector<int>& nums, int left, int right)
    {
        int randomIdx = rand() % (right - left + 1) + left;
        swap(nums[left], nums[randomIdx]);
        int pivot = nums[left];
        while(left < right)
        {
            while(left < right && to_string(nums[right]) >= to_string(pivot))
                --right;
            nums[left] = nums[right];
            while(left < right && to_string(nums[left]) <= to_string(pivot))
                ++left;
            nums[right] = nums[left];
        }
        nums[left] = pivot;
        return left;
    }

    void quickSelect(vector<int>& nums, int left, int right, int k)
    {
        if(left >= right)
            return;

        int pivot = partition(nums, left, right);
        if(pivot == k - 1)
            return;
        else if(pivot > k - 1)
            quickSelect(nums, left, pivot - 1, k);
        else
            quickSelect(nums, pivot + 1, right, k);
    }
public:
    int findKthNumber(int n, int k) {
        vector<int> nums(n, 0);
        for(int i = 1; i <= n; ++i)
            nums[i - 1] = i;
        quickSelect(nums, 0, n - 1, k);
        return nums[k - 1];
    }
};

解法二：十叉树

算法流程：

• 初始化：当前前缀 prefix = 1，当前前缀是字典序第 count = 1 小的数
• 如果 count < k，则迭代查找
  • 获取当前前缀 prefix 的子节点（含本身）个数 curCount
  • 如果 count + curCount > k，说明字典序第 k 小的数在当前前缀的子树中
    • 前缀 prefix = prefix * 10，即移动到下一层的第一个节点。eg. 原本前缀为 1，则变为 10；原本前缀为 10，则变为 100
    • 更新 count = count + 1，代表当前前缀是字典序第 count 小的数。eg. 原本前缀 1 是字典序第 1 小的数，那么前缀 10 是字典序第 2 小的数
  • 否则，说明字典序第 k 小的数不在当前前缀的子树中，应该去下一个前缀的子树中查找
    • 前缀 prefix = prefix + 1，即移动到当前层的下一个节点。eg. 原本前缀为 1，则变为 2；原本前缀为 10，则变为 11
    • 更新 count = count + curCount

例：设n = 111，k = 13
第一轮查找：当前前缀 prefix = 1，是字典序第 count = 1 小的数

• 查找前缀 prefix 为 1 的子节点个数 curCount = 23（调用 long long getCountOfPrefix(long long prefix, long long n) 函数的过程如下）

• count + curCount = 1 + 23 = 24 > k = 13，因此字典序第 k 小的数在当前前缀的子树中，前缀 prefix 移动到下一层的第一个节点，即 prefix = prefix * 10 = 10，且 count = count + 1 = 2，即当前前缀 prefix = 10 是字典序第 2 小的数

第二轮查找：当前前缀 prefix = 10，是字典序第 count = 2 小的数

• 查找前缀 prefix 为 10 的子节点个数 curCount = 11
• count + curCount = 2 + 11 = 13 <= k = 13，因此字典序第 k 小的数不在当前前缀的子树中，应该去右边下一个前缀的树中查找，前缀 prefix = prefix + 1 = 11，count = count + 11 = 13，即当前前缀 prefix = 11 是字典序第 13 小的数

第三轮查找，当前前缀 prefix = 11，是字典序第 count = 13 小的数，count == k，因此结束查找，prefix = 11 就是字典序第 13 小的数

class Solution {
private:
    // 查找前缀为 prefix 的子节点（含前缀本身）个数，另外还要限制子节点的大小不超过 n
    // 使用 long long 是防止 int 溢出
    long long getCountOfPrefix(long long prefix, long long n)
    {
        long long count = 0;                // 前缀为 prefix 的子节点个数
        long long nextPrefix = prefix + 1;    // 下一个前缀，就是当前缀的值 + 1
        // 子节点的大小不能超过上界 n
        while(prefix <= n)
        {
            count += min(n + 1, nextPrefix) - prefix;    // 当前前缀这一层的节点数
            prefix = prefix * 10;                        
            nextPrefix = nextPrefix * 10;
        }
        return count;
    }
public:
    int findKthNumber(int n, int k) {
        long long prefix = 1;    // 当前的前缀
        long long count = 1;    // 当前前缀是字典序第 count 小的数
        while(count < k)
        {
            // 获取当前前缀的子节点数
            long long curCount = getCountOfPrefix(prefix, n);
            // 如果字典序第 k 小的数在当前前缀的子孙节点中
            if(count + curCount > k)
            {
                prefix *= 10;    // 前缀*10，即移到下一层的第一个节点中查找
                ++count;        // 当前的前缀是字典序第 count 小的数
            }
            // 如果字典序第 k 小的数不在当前前缀的子孙节点中
            else
            {
                prefix += 1;        // 去下一个前缀的树中查找
                count += curCount;    // 更新 count
            }
        }
        return prefix;
    }
};

执行结果：

执行结果：通过

执行用时：0 ms, 在所有 C++ 提交中击败了 100.00% 的用户
内存消耗：5.8 MB, 在所有 C++ 提交中击败了 62.30% 的用户