版本号排序

题目描述

爱丽丝在人偶制作的过程中，为了方便维护众多的“上海人偶”，为每个人偶标记了不同的版本号。随着人偶版本的更迭，版本号的排布变得十分混乱，她需要你帮忙将这些版本号按从小到大进行整理。

版本号格式：

1. 主版本号：由 1 至 4 个非负整数组成，整数之间用 . 分隔（例如 1.0.2），每个部分的值在 [0, 1000] 范围内，不含多余前导零。
2. 测试版本号（可选）：位于主版本号之后，以空格分隔，格式为 betaX，其中 X 为正整数（例如 1.0.2 beta3）。若不包含此部分，则该版本为正式版。

排序规则：

1. 先比较主版本号：从左至右依次比较对应位置的整数。若在某个位置数字不同，数字较小者排前面；若一个主版本号是另一个的前缀且两者长度不同，则较短者较小（例如 1.0 < 1.0.0）。
2. 当主版本号完全相同时：
   • 测试版总是小于正式版（例如 1.0.0 beta9 < 1.0.0）
   • 若两者均为测试版，则比较 beta 后续的整数 X，数字较小者排前面

示例

输入：

5
1.0.1.0
1.0.0.0 beta3
1.0.0.1 beta1
1.0.0.0 beta2
1.0.0.1

输出：

1.0.0.0 beta2
1.0.0.0 beta3
1.0.0.1 beta1
1.0.0.1
1.0.1.0

说明：

• 首先比较主版本号：1.0.0.0 的部分位数字小于 1.0.0.1 和 1.0.1.0，故排在最前。
• 对于主版本号同为 1.0.0.0 的两个版本，比较测试版编号：由于 2 < 3，故 beta2 排在 beta3 之前。
• 对于主版本号同为 1.0.0.1 的两个版本，测试版 beta1 必须小于正式版。

解题思路

核心在于自定义比较器：

主版本号比较： 将版本号按 . 分割，补齐到 4 位（缺失位用 -1 填充，因为 -1 小于任何合法值 0~1000，这样能保证短版本 < 长版本），然后逐段比较。

测试版处理： 正式版的 betaNum 设为 Infinity，确保排在所有测试版后面。测试版解析 beta 后面的数字作为 betaNum。

排序过程：

1. 解析输入，将每个版本号拆分为 {version, betaNum} 结构体
2. 调用 sort 传入自定义比较器
3. 比较器中：先逐段比较主版本号，若相同再比较 betaNum
4. 输出时重新拼接 version 和 beta 后缀

代码实现

/**
 * 版本号比较器
 * - 主版本号逐段比较，缺失段视为 -1（小于任何合法值 0~1000，保证短版本 < 长版本）
 * - 主版本号相同时：测试版 < 正式版；同为测试版比较 beta 编号
 */
const compareHandle = (pre, next) => {
    const preList = pre.version.split(".");
    const nextList = next.version.split(".");

    // 补齐到 4 位，缺失位用 -1 填充（-1 < 任何合法值 0~1000）
    const preVer = Array.from({ length: 4 }, (_, k) =>
        k < preList.length ? Number(preList[k]) : -1
    );
    const nextVer = Array.from({ length: 4 }, (_, k) =>
        k < nextList.length ? Number(nextList[k]) : -1
    );

    // 逐段比较主版本号
    for (let i = 0; i < 4; i++) {
        if (preVer[i] !== nextVer[i]) {
            return preVer[i] - nextVer[i];
        }
    }

    // 主版本号相同，比较 beta 编号（正式版 betaNum=Infinity，确保排最后）
    return pre.betaNum - next.betaNum;
};

function versionSort(inputs) {
    const versions = [];
    for (const line of inputs) {
        const versionSplit = line.split(" ");
        const version = versionSplit[0];
        let betaNum = Infinity;
        if (versionSplit.length > 1) {
            betaNum = parseInt(versionSplit[1].replace("beta", ""), 10);
        }
        versions.push({ version, betaNum });
    }

    versions.sort(compareHandle);

    return versions.map(({ version, betaNum }) =>
        betaNum !== Infinity ? version + " beta" + betaNum : version
    );
}

复杂度分析

• 时间复杂度： O(n log n · k)，其中 n 为版本号数量（≤100），k 为比较复杂度（常量，最多 4 段）。实际效率很高。
• 空间复杂度： O(n)，存储解析后的版本号数组。

5
1.0.1.0
1.0.0.0 beta3
1.0.0.1 beta1
1.0.0.0 beta2
1.0.0.1

1.0.0.0 beta2
1.0.0.0 beta3
1.0.0.1 beta1
1.0.0.1
1.0.1.0