数据库ID路径字符串构建：算法优化与斜杠数量限制

问题概述 #

我们需要为大于0的整数ID生成特定格式的文件夹路径：按数位拆分数字为范围段，用斜杠分隔，必须恰好包含6个斜杠（即6级路径）。例如：

• 输入123456 → 输出 100000-199999/20000-29999/3000-3999/400-499/50-59/6/
• 输入1234567890 → 输出 1234500000-1234599999/60000-69999/7000-7999/800-899/90-99/0/

现有一段PHP朴素实现，复杂度为O(n)，需解决两个核心问题：

1. 强制限制结果为6个斜杠对应6级路径
2. 将算法复杂度优化至O(log(n))

原朴素实现代码：

<?php

function produceString(int $n) {
    $ranges = array();
    $k = strlen(strval($n)) - 1;
    while ($k >= 0) {
        $a = floor($n / pow(10, $k)) * pow(10, $k);
        $b = $a + pow(10, $k) - 1;
        array_push($ranges, $a == $b ? "$a" : "$a-$b");
        $n = $n % pow(10, $k);
        $k -= 1;
    }
    return implode("/", $ranges);
}

解决方案与优化代码 #

问题1：固定生成6级路径（6个斜杠）

核心逻辑：

• 若ID的数位长度超过6，将前数位长度-5位合并为第一个范围段，剩余5位依次拆分，刚好凑够6段
• 若ID的数位长度不足6，拆分所有数位后，用0填充剩余分段，确保最终是6段

问题2：复杂度优化至O(log(n))

原代码的性能瓶颈：

• 依赖字符串转换计算数位长度，额外增加开销
• 循环次数等于数位长度，而我们只需要固定循环最多6次（常数次）

优化思路：

• 用数学函数log10直接计算数位长度，避免字符串转换
• 固定循环次数为6次（或更少，剩余用0填充），时间复杂度降为O(log(n))（每次处理涉及10的幂次运算，属于对数级操作）

优化后的PHP代码：

<?php

function produceFolderPath(int $n): string {
    $ranges = [];
    $remaining = $n;
    // 计算数字总位数（避免字符串转换）
    $totalDigits = $remaining > 0 ? floor(log10($remaining)) + 1 : 1;

    // 处理第一段：位数超6则合并高位
    if ($totalDigits > 6) {
        $firstSegDigits = $totalDigits - 5;
        $divisor = pow(10, $firstSegDigits);
        $lower = intdiv($remaining, $divisor) * $divisor;
        $upper = $lower + $divisor - 1;
        $ranges[] = $lower === $upper ? (string)$lower : "$lower-$upper";
        $remaining = $remaining % $divisor;
        $remainingLoops = 5;
    } else {
        $remainingLoops = 6;
    }

    // 处理剩余分段，补0至6段
    for ($i = 0; $i < $remainingLoops; $i++) {
        if ($remaining === 0) {
            $ranges[] = "0";
            continue;
        }
        $currentDigits = floor(log10($remaining)) + 1;
        $divisor = pow(10, $currentDigits - 1);
        $lower = intdiv($remaining, $divisor) * $divisor;
        $upper = $lower + $divisor - 1;
        $ranges[] = $lower === $upper ? (string)$lower : "$lower-$upper";
        $remaining = $remaining % $divisor;
    }

    // 确保刚好6段，拼接后添加末尾斜杠
    return implode("/", array_slice($ranges, 0, 6)) . "/";
}

验证示例 #

• 输入123456 → 输出 100000-199999/20000-29999/3000-3999/400-499/50-59/6/
• 输入1234567890 → 输出 1234500000-1234599999/60000-69999/7000-7999/800-899/90-99/0/
• 输入123 → 输出 100-199/20-29/3/0/0/0/

内容的提问来源于stack exchange，提问作者Rusurano