Medium

题目描述

给你两个版本号字符串 version1 和 version2，请比较它们。版本号由一个或多个修订号组成，各修订号由一个 ‘.’ 连接。每个修订号由多位数字组成，可能包含前导零。每个版本号至少包含一个字符。修订号从左到右编号，下标从 0 开始，最左边的修订号下标为 0，下一个修订号下标为 1，以此类推。

比较版本号时，请按从左到右的顺序依次比较它们的修订号。比较修订号时，只需比较忽略任何前导零后的整数值。也就是说，修订号 “1” 和修订号 “001” 相等。如果版本号没有指定某个下标处的修订号，则该修订号视为 0。

根据以下规则，返回结果：

  • 如果 version1 < version2 返回 -1
  • 如果 version1 > version2 返回 1
  • 否则返回 0

示例 1：

输入: version1 = "1.2", version2 = "1.10"
输出: -1
解释: version1 的第二个修订号是 "2"，version2 的第二个修订号是 "10"：2 < 10，所以 version1 < version2。

示例 2：

输入: version1 = "1.01", version2 = "1.001"
输出: 0
解释: 忽略前导零，"01" 和 "001" 都表示相同的整数 "1"。

示例 3：

输入: version1 = "1.0", version2 = "1.0.0.0"
输出: 0
解释: version1 没有指定下标为 2 和 3 的修订号，即视为 "0"。

提示：

  • 1 <= version1.length, version2.length <= 500
  • version1 和 version2 仅包含数字和 ‘.’
  • version1 和 version2 都是有效的版本号
  • version1 和 version2 的所有修订号都可以存储在 32 位整数中

解题思路

解题思路

本题需要按位置比较两个版本号的每个修订号。主要有两种解法：

方法一：字符串分割（推荐）

  1. 使用分隔符 ‘.’ 将两个版本号分别分割成修订号数组
  2. 逐个比较对应位置的修订号，将字符串转换为整数进行比较
  3. 如果某个版本号的修订号较少，缺失的部分视为 0

方法二：双指针

  1. 使用两个指针分别遍历两个版本号字符串
  2. 每次提取一个修订号并转换为整数进行比较
  3. 跳过分隔符 ‘.’，继续比较下一个修订号

两种方法的时间复杂度相同，但分割方法更简洁易懂。需要注意的关键点：

  • 修订号可能有前导零，需要转换为整数比较
  • 版本号长度可能不同，缺失部分按 0 处理
  • 比较结果返回 -1、0、1 三种情况

代码实现

class Solution {
public:
    int compareVersion(string version1, string version2) {
        vector<int> v1 = split(version1);
        vector<int> v2 = split(version2);
        
        int n = max(v1.size(), v2.size());
        for (int i = 0; i < n; i++) {
            int rev1 = i < v1.size() ? v1[i] : 0;
            int rev2 = i < v2.size() ? v2[i] : 0;
            if (rev1 < rev2) return -1;
            if (rev1 > rev2) return 1;
        }
        return 0;
    }
    
private:
    vector<int> split(string version) {
        vector<int> result;
        int start = 0;
        for (int i = 0; i <= version.length(); i++) {
            if (i == version.length() || version[i] == '.') {
                result.push_back(stoi(version.substr(start, i - start)));
                start = i + 1;
            }
        }
        return result;
    }
};

class Solution:
    def compareVersion(self, version1: str, version2: str) -> int:
        v1 = list(map(int, version1.split('.')))
        v2 = list(map(int, version2.split('.')))
        
        n = max(len(v1), len(v2))
        for i in range(n):
            rev1 = v1[i] if i < len(v1) else 0
            rev2 = v2[i] if i < len(v2) else 0
            if rev1 < rev2:
                return -1
            elif rev1 > rev2:
                return 1
        return 0

public class Solution {
    public int CompareVersion(string version1, string version2) {
        string[] v1 = version1.Split('.');
        string[] v2 = version2.Split('.');
        
        int n = Math.Max(v1.Length, v2.Length);
        for (int i = 0; i < n; i++) {
            int rev1 = i < v1.Length ? int.Parse(v1[i]) : 0;
            int rev2 = i < v2.Length ? int.Parse(v2[i]) : 0;
            if (rev1 < rev2) return -1;
            if (rev1 > rev2) return 1;
        }
        return 0;
    }
}

var compareVersion = function(version1, version2) {
    const v1 = version1.split('.').map(Number);
    const v2 = version2.split('.').map(Number);
    
    const n = Math.max(v1.length, v2.length);
    for (let i = 0; i < n; i++) {
        const rev1 = i < v1.length ? v1[i] : 0;
        const rev2 = i < v2.length ? v2[i] : 0;
        if (rev1 < rev2) return -1;
        if (rev1 > rev2) return 1;
    }
    return 0;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度说明
时间复杂度O(n + m)n 和 m 分别是两个版本号字符串的长度，需要遍历整个字符串进行分割和比较
空间复杂度O(n + m)需要额外空间存储分割后的修订号数组