Lexicographical Numbers ใน C++: เรียงตัวเลข 1 ถึง n แบบ Dictionary Order

โจทย์

กำหนดจำนวนเต็ม n คืนอาร์เรย์ตัวเลข 1 ถึง n เรียงตามลำดับเลขศัพท์ (Lexicographical Order)

ตัวอย่าง: n = 13 → [1, 10, 11, 12, 13, 2, 3, 4, 5, 6, 7, 8, 9]

แนวคิด: DFS / Pre-order Traversal บนต้นไม้ 10 แยก

จินตนาการต้นไม้ที่รากคือ 1-9 แต่ละโหนดมีลูก 10 ตัว (เพิ่มหลักท้าย 0-9) การเดิน Pre-order จะได้ลำดับ Lexicographical

ขั้นตอนแบบ Iterative (O(1) space)

1. curr = 1
2. ลูป i = 0 ถึง n-1:
   • เพิ่ม curr ลงผลลัพธ์
   • ถ้า curr * 10 <= n → curr *= 10 (ลงลึก)
   • มิฉะนั้น:
     • ถ้า curr >= n → curr /= 10 (ขึ้นบน)
     • curr++ (ไปโหนดถัดไป)
     • while curr % 10 == 0 → curr /= 10 (ข้ามเลขที่ลงท้าย 0 เช่น 19→20→2)

ตัวอย่างโค้ด C++

#include <bits/stdc++.h>
using namespace std;

void print_vector(vector<int> v) {
    cout << "[";
    for (int i = 0; i < v.size(); i++) cout << v[i] << ", ";
    cout << "]" << endl;
}

class Solution {
public:
    vector<int> lexicalOrder(int n) {
        vector<int> ret(n);
        int curr = 1;
        for (int i = 0; i < n; i++) {
            ret[i] = curr;
            if (curr * 10 <= n) {
                curr *= 10;
            } else {
                if (curr >= n) curr /= 10;
                curr++;
                while (curr % 10 == 0) curr /= 10;
            }
        }
        return ret;
    }
};

int main() {
    Solution ob;
    print_vector(ob.lexicalOrder(20));
    return 0;
}

อินพุต / เอาต์พุต

Input: 20

Output: [1, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 2, 20, 3, 4, 5, 6, 7, 8, 9]

ความซับซ้อน

• Time: O(n) - แต่ละตัวเลขประมวลผล 1 ครั้ง
• Space: O(1) extra (ไม่นับ output)