Hard

题目描述

给定两个整数 n 和 k，返回在范围 [1, n] 中第 k 个按字典序排列的最小整数。

示例 1：

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

示例 2：

输入：n = 1, k = 1
输出：1

约束条件：

  • 1 <= k <= n <= 10^9

解题思路

这道题考查的是字典序遍历和前缀树的思想。

核心思路：

字典序本质上是按照前缀树的深度优先搜索顺序排列的。比如对于n=13，字典序为：1, 10, 11, 12, 13, 2, 3, 4, 5, 6, 7, 8, 9。

我们可以把这个问题转化为：在前缀树中找到第k个节点。关键是要能快速计算以某个前缀开头的数字有多少个。

算法步骤：

  1. 从根节点1开始（字典序最小）
  2. 对于当前前缀，计算以它为根的子树中有多少个节点
  3. 如果这个数量小于k，说明答案不在这个子树中，跳到下一个兄弟节点
  4. 如果数量大于等于k，说明答案在这个子树中，深入到子节点继续查找

计算子树节点数的方法： 对于前缀prefix，计算[prefix, prefix+1)范围内在[1,n]中的数字个数。通过层层计算：prefix, prefix10, prefix100…直到超出n为止。

时间复杂度： O(log²n)，外层循环最多logn次，内层计算节点数也是logn次。 空间复杂度： O(1)。

代码实现

class Solution {
public:
    int findKthNumber(int n, int k) {
        long curr = 1;
        k--;  // 因为我们从1开始，所以k要减1
        
        while (k > 0) {
            long steps = countSteps(n, curr, curr + 1);
            if (steps <= k) {
                // 跳过整个子树，移动到下一个兄弟节点
                curr++;
                k -= steps;
            } else {
                // 深入到子节点
                curr *= 10;
                k--;
            }
        }
        
        return curr;
    }
    
private:
    long countSteps(long n, long prefix1, long prefix2) {
        long steps = 0;
        while (prefix1 <= n) {
            steps += min(n + 1, prefix2) - prefix1;
            prefix1 *= 10;
            prefix2 *= 10;
        }
        return steps;
    }
};

class Solution:
    def findKthNumber(self, n: int, k: int) -> int:
        def count_steps(n, prefix1, prefix2):
            steps = 0
            while prefix1 <= n:
                steps += min(n + 1, prefix2) - prefix1
                prefix1 *= 10
                prefix2 *= 10
            return steps
        
        curr = 1
        k -= 1  # 因为我们从1开始，所以k要减1
        
        while k > 0:
            steps = count_steps(n, curr, curr + 1)
            if steps <= k:
                # 跳过整个子树，移动到下一个兄弟节点
                curr += 1
                k -= steps
            else:
                # 深入到子节点
                curr *= 10
                k -= 1
        
        return curr

public class Solution {
    public int FindKthNumber(int n, int k) {
        long curr = 1;
        k--;  // 因为我们从1开始，所以k要减1
        
        while (k > 0) {
            long steps = CountSteps(n, curr, curr + 1);
            if (steps <= k) {
                // 跳过整个子树，移动到下一个兄弟节点
                curr++;
                k -= (int)steps;
            } else {
                // 深入到子节点
                curr *= 10;
                k--;
            }
        }
        
        return (int)curr;
    }
    
    private long CountSteps(long n, long prefix1, long prefix2) {
        long steps = 0;
        while (prefix1 <= n) {
            steps += Math.Min(n + 1, prefix2) - prefix1;
            prefix1 *= 10;
            prefix2 *= 10;
        }
        return steps;
    }
}

var findKthNumber = function(n, k) {
    function countSteps(n, prefix1, prefix2) {
        let steps = 0;
        while (prefix1 <= n) {
            steps += Math.min(n + 1, prefix2) - prefix1;
            prefix1 *= 10;
            prefix2 *= 10;
        }
        return steps;
    }
    
    let curr = 1;
    k--;  // 因为我们从1开始，所以k要减1
    
    while (k > 0) {
        let steps = countSteps(n, curr, curr + 1);
        if (steps <= k) {
            // 跳过整个子树，移动到下一个兄弟节点
            curr++;
            k -= steps;
        } else {
            // 深入到子节点
            curr *= 10;
            k--;
        }
    }
    
    return curr;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度说明
时间复杂度O(log²n)外层while循环最多执行logn次，内层countSteps函数也需要logn时间
空间复杂度O(1)只使用常数级别的额外空间

相关题目