题解 | #软件版本交叉排序#

题目链接

软件版本交叉排序

题目描述

给定一批格式为 major.minor.patch.build 的软件版本号，你需要对它们进行一种特殊的“交叉排序”。

版本号比较规则:

版本号由四个整数部分组成，比较时遵循字典序。
先比较主版本号 major，数值小者版本低。
若主版本号相同，则比较次版本号 minor，以此类推，直到构建号 build。

排序输出规则:

最终的输出顺序应为：最小版本号、最大版本号、第二小版本号、第二大版本号、...

输入:

第一行一个整数 $N$ ，表示版本号的数量。
接下来 $N$ 行，每行一个版本号字符串。

输出:

一行字符串，包含交叉排序后的版本号，用单个空格分隔。

解题思路

这个问题可以分解为两个主要步骤：首先对版本号进行标准排序，然后根据排序结果生成交叉序列。

版本号的解析与排序
- 解析: 版本号字符串（如 "35.107.224.55"）不适合直接进行字符串比较，因为 "80" 会小于 "101"，但字符串 "80.x" 会大于 "101.x"。因此，我们需要将每个版本号字符串解析为其四个整数部分。
- 数据结构: 我们可以创建一个 Version 类或结构体来存储这四个整数，并保留原始的字符串形式以便输出。
- 排序:
  - C++: 重载 operator< 或者提供一个自定义的比较函数给 std::sort。
  - Java: 让 Version 类实现 Comparable 接口，并重写 compareTo 方法。
  - Python: sort 函数的 key 参数非常适合此场景。我们可以提供一个 lambda 函数，它将版本号字符串分割 split('.') 并将各部分转换为整数元组 (int(v) for v in version_str.split('.'))。Python 会自动对元组进行字典序比较。
- 完成这一步后，我们就得到了一个从低到高排好序的版本号列表。
生成交叉序列 (双指针法)
- 对排好序的列表，我们可以使用两个指针， $left$ 指向列表的开头（最小元素）， $right$ 指向列表的末尾（最大元素）。
- 创建一个新的列表 result 来存放交叉排序的结果。
- 进入一个循环，条件是 $left \le right$ ： a. 首先，将 $left$ 指向的元素（当前最小）添加到 result 中，然后 $left$ 指针向右移动一位 (left++)。 b. 检查 $left$ 是否仍然小于等于 $right$ （这对于奇数个元素的情况很重要）。如果是，则将 $right$ 指向的元素（当前最大）添加到 result 中，然后 $right$ 指针向左移动一位 (right--)。
- 循环结束后，result 列表中的顺序就是题目要求的交叉顺序。
输出
- 将 result 列表中的版本号字符串用空格连接并输出。

代码

cpp
java
python

#include <iostream>
#include <vector>
#include <string>
#include <sstream>
#include <algorithm>

using namespace std;

struct Version {
    string original_str;
    vector<int> parts;

    bool operator<(const Version& other) const {
        return parts < other.parts;
    }
};

Version parse_version(const string& s) {
    Version v;
    v.original_str = s;
    stringstream ss(s);
    string item;
    while (getline(ss, item, '.')) {
        v.parts.push_back(stoi(item));
    }
    return v;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    int n;
    cin >> n;
    vector<Version> versions(n);
    for (int i = 0; i < n; ++i) {
        string s;
        cin >> s;
        versions[i] = parse_version(s);
    }

    sort(versions.begin(), versions.end());

    vector<string> result;
    int left = 0, right = n - 1;
    while (left <= right) {
        result.push_back(versions[left++].original_str);
        if (left <= right) {
            result.push_back(versions[right--].original_str);
        }
    }

    for (int i = 0; i < result.size(); ++i) {
        cout << result[i] << (i == result.size() - 1 ? "" : " ");
    }
    cout << endl;

    return 0;
}

import java.util.Scanner;
import java.util.ArrayList;
import java.util.List;
import java.util.Collections;
import java.util.stream.Collectors;
import java.util.stream.Stream;

class Version implements Comparable<Version> {
    String originalStr;
    List<Integer> parts;

    public Version(String s) {
        this.originalStr = s;
        this.parts = Stream.of(s.split("\\."))
                           .map(Integer::parseInt)
                           .collect(Collectors.toList());
    }

    @Override
    public int compareTo(Version other) {
        for (int i = 0; i < 4; i++) {
            if (!this.parts.get(i).equals(other.parts.get(i))) {
                return this.parts.get(i).compareTo(other.parts.get(i));
            }
        }
        return 0;
    }
}

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        List<Version> versions = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            versions.add(new Version(sc.next()));
        }

        Collections.sort(versions);

        List<String> result = new ArrayList<>();
        int left = 0, right = n - 1;
        while (left <= right) {
            result.add(versions.get(left++).originalStr);
            if (left <= right) {
                result.add(versions.get(right--).originalStr);
            }
        }

        System.out.println(String.join(" ", result));
    }
}

def main():
    n = int(input())
    versions = [input() for _ in range(n)]

    # 使用 lambda 函数和元组进行字典序排序
    versions.sort(key=lambda v: tuple(map(int, v.split('.'))))

    result = []
    left, right = 0, n - 1
    while left <= right:
        result.append(versions[left])
        left += 1
        if left <= right:
            result.append(versions[right])
            right -= 1
            
    print(" ".join(result))

if __name__ == "__main__":
    main()

算法及复杂度

算法：自定义排序 + 双指针
时间复杂度： $\mathcal{O}(N \log N)$ 。瓶颈在于对 $N$ 个版本号进行排序。版本号的解析和比较是常数时间（因为只有4个部分）。双指针生成交叉序列的过程是 $\mathcal{O}(N)$ 。
空间复杂度： $\mathcal{O}(N)$ 。需要存储 $N$ 个版本号及其解析后的整数部分，以及最终的结果列表。