ค่าที่ k เล็กสุดแบบเล็กซิโครกราฟิกใน C++

ภาพรวมปัญหา

หาตัวเลขที่ k เล็กสุดในลำดับเลข 1 ถึง n เมื่อเรียงตามลำดับเล็กซิโครกราฟิก (lexicographical order)

ตัวอย่าง

n = 14, k = 3
ลำดับ: [1, 10, 11, 12, 13, 14, 2, 3, 4, 5, 6, 7, 8, 9]
ตัวที่ 3 คือ 11

วิธีแก้ปัญหา: นับขั้นตอนระหว่างพรีฟิกซ์

พิจารณาต้นไม้ทริ (Trie) ของตัวเลข 1 ถึง n แต่ละโหนดคือตัวเลข ลูกคือการต่อท้ายด้วย 0-9
ใช้ฟังก์ชัน calcSteps(n, n1, n2) นับจำนวนตัวเลขระหว่างพรีฟิกซ์ n1 และ n2

ขั้นตอนหลัก

1. เริ่มที่ curr = 1, k-- (เพราะนับ 1 ไปแล้ว)
2. เมื่อ 0:
   • steps = calcSteps(n, curr, curr + 1)
   • ถ้า steps <= k → ข้ามต้นไม้ย่อยนี้ไป: k -= steps, curr++
   • ถ้า steps > k → เข้าไปลึกกว่า: curr *= 10, k--
3. คืนค่า curr

ฟังก์ชัน calcSteps

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;
}

โค้ด 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));
}

การวิเคราะห์ความซับซ้อน

• เวลา: O((log n)²) — ความลึกของต้นไม้ × การคำนวณ steps
• พื้นที่: O(1)