Số nhỏ thứ k theo thứ tự từ điển trong C++

Cho n và k, tìm số nguyên thứ k theo thứ tự từ điển (lexicographical) trong khoảng [1, n].

Ví dụ

n = 14, k = 3

Thứ tự từ điển: [1, 10, 11, 12, 13, 14, 2, 3, 4, 5, 6, 7, 8, 9]

Số thứ 3 là 11.

Thuật toán: Duyệt cây tiền tố (Prefix Tree)

Xem các số như các nút trên cây 10 nhánh (0-9). Duyệt theo pre-order để tìm nút thứ k.

1. Khởi tạo curr = 1, giảm k-- (vì đã tính 1).
2. Khi 0:
   • Tính steps = số nút trong cây con gốc curr (giữa curr và curr+1).
   • Nếu steps ≤ k: bỏ qua toàn bộ cây con này, k -= steps, curr++ (chuyển sang anh em tiếp theo).
   • Ngược lại: đi sâu vào cây con, curr *= 10, k--.
3. Trả về curr.

Tính steps (số nút giữa curr và curr+1)

int calcSteps(long long n, long long n1, long long n2) {
    int ret = 0;
    while (n1 <= n) {
        ret += min(n + 1, n2) - n1;
        n1 *= 10;
        n2 *= 10;
    }
    return ret;
}

Cài đặt C++

#include <bits/stdc++.h>
using namespace std;
typedef long long int lli;

class Solution {
public:
    int findKthNumber(int n, int k) {
        int curr = 1;
        k--;
        while (k) {
            int steps = calcSteps(n, curr, curr + 1);
            if (steps <= k) {
                k -= steps;
                curr++;
            } else {
                curr *= 10;
                k -= 1;
            }
        }
        return curr;
    }

    int calcSteps(lli nax, lli n1, lli n2) {
        int ret = 0;
        while (n1 <= nax) {
            ret += min(nax + 1, n2) - n1;
            n1 *= 10;
            n2 *= 10;
        }
        return ret;
    }
};

int main() {
    Solution ob;
    cout << ob.findKthNumber(14, 3);
    return 0;
}

Độ phức tạp

• Thời gian: O(log n) — mỗi bước hoặc tăng curr hoặc nhân 10, chiều cao cây ~ log10(n).
• Không gian: O(1).

Input / Output

Input:  14, 3
Output: 11