题解 | 字典序

#include <iostream>
using namespace std;

class Solution {
public:
    // 计算[1,n]范围内以prefix为前缀的数字个数
    long long countNumbers(long long prefix, long long n) {
        long long current = prefix;
        long long next = prefix + 1;
        long long count = 0;
        
        while (current <= n) {
            count += min(next, n + 1) - current;
            current *= 10;
            next *= 10;
        }
        return count;
    }
    
    long long findKthNumber(long long n, long long m) {
        long long current = 1;  // 从1开始查找
        m--;  // 因为从1开始，所以m需要减1
        
        while (m > 0) {
            long long step = countNumbers(current, n);
            
            if (step <= m) {
                m -= step;
                current++;
            } else {
                m--;
                current *= 10;
            }
        }
        return current;
    }
};

int main() {
    long long n, m;
    cin >> n >> m;
    Solution solution;
    cout << solution.findKthNumber(n, m) << endl;
    return 0;
}

import java.util.*;

public class Main {
    static class Solution {
        // 计算[1,n]范围内以prefix为前缀的数字个数
        public long countNumbers(long prefix, long n) {
            long current = prefix;
            long next = prefix + 1;
            long count = 0;
            
            while (current <= n) {
                count += Math.min(next, n + 1) - current;
                current *= 10;
                next *= 10;
            }
            return count;
        }
        
        public long findKthNumber(long n, long m) {
            long current = 1;  // 从1开始查找
            m--;  // 因为从1开始，所以m需要减1
            
            while (m > 0) {
                long step = countNumbers(current, n);
                
                if (step <= m) {
                    m -= step;
                    current++;
                } else {
                    m--;
                    current *= 10;
                }
            }
            return current;
        }
    }
    
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        long n = sc.nextLong();
        long m = sc.nextLong();
        Solution solution = new Solution();
        System.out.println(solution.findKthNumber(n, m));
    }
}

def count_numbers(prefix: int, n: int) -> int:
    """计算[1,n]范围内以prefix为前缀的数字个数"""
    current = prefix
    next_prefix = prefix + 1
    count = 0
    
    while current <= n:
        count += min(next_prefix, n + 1) - current
        current *= 10
        next_prefix *= 10
        
    return count

def find_kth_number(n: int, m: int) -> int:
    """找到字典序第m小的数"""
    current = 1  # 从1开始查找
    m -= 1  # 因为我们从1开始，所以m需要减1
    
    while m > 0:
        step = count_numbers(current, n)
        
        if step <= m:
            m -= step
            current += 1
        else:
            m -= 1
            current *= 10
            
    return current

if __name__ == "__main__":
    n, m = map(int, input().split())
    print(find_kth_number(n, m))