LeetCode 440: 字典序的第K小数字

[guodongxiaren]

https://leetcode-cn.com/problems/k-th-smallest-in-lexicographical-order

字典序的第K小数字

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

注意：1 ≤ k ≤ n ≤ 109。

示例 :

输入: n: 13 k: 2

输出: 10

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

[guodongxiaren]

快速排序+自定义比较运算 堆+自定义比较运算 都会超时。 这道题很特殊要利用字典序的一些特征。实现10叉树。

[guodongxiaren]

class Solution {
public:
    int findKthNumber(int n, int k) {
        auto getCount = [](int 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;
        };

        int prefix = 1;
        long count = 1;
        while (count < k) {
            long c = getCount(prefix, n);
            if (count + c > k) {
                prefix *= 10;
                count ++;
            } else {
                prefix++;
                count += c;
            }
        }
        return prefix;
    }
};

leetcode 题目都可以用lambda来定义辅助函数，不用新增成员变量了。

[guodongxiaren]

题解：

https://leetcode-cn.com/problems/k-th-smallest-in-lexicographical-order/solution/ben-ti-shi-shang-zui-wan-zheng-ju-ti-de-shou-mo-sh/

这道题比较Trick。只适用于数字的字典序。多了字母就不好搞了。

注意。C++存在的溢出问题，主要是在最后一次*10的时候。另外std::min不支持long和int的比较大小！