题解 | #比较版本号#

算法思想一：分割+遍历

解题思路：

将两个字符串按点字符分割成块，然后逐个比较这些块

如果两个版本号的块数相同，则可以有效工作。如果不同，则需要在较短字符串末尾补充相应的 .0 块数使得块数相同。

算法：
1、根据点分割两个字符串将分割的结果存储到数组中。
2、遍历较长数组并逐个比较块。如果其中一个数组结束了，实际上可以根据需要添加尽可能多的零，以继续与较长的数组进行比较。
3、如果两个版本号不同，则返回 1 或 -1。
4、版本号相同，返回 0。

代码展示：

Python版本

class Solution:
    def compare(self , version1 , version2 ):
        # write code here
        # 以点为分割点进行分割
        nums1 = version1.split('.')
        nums2 = version2.split('.')
        n1, n2 = len(nums1), len(nums2)
        # compare versions
        # 遍历长度较长的分割数组
        for i in range(max(n1, n2)):
            # 遍历对比 i1 i2,数组遍历完后加0继续
            i1 = int(nums1[i]) if i < n1 else 0
            i2 = int(nums2[i]) if i < n2 else 0
            if i1 != i2:
                # 如果 i1 i2不同，则进行比较大小判断结果
                return 1 if i1 > i2 else -1
        # the versions are equal 版本号相同
        return 0

复杂度分析

时间复杂度 $O(N+M)$ 。其中 $N$ 和 $M$ 指的是输入字符串的长度。分割字符串时间 $O(N+M)$ )，遍历分割后的结果时间 $O(max(N,M))$

空间复杂的 $O(N+M)$ ：使用了两个数组 $nums1$ 和 $nums2$ 存储两个字符串的块。

算法思想二：双指针+遍历

解题思路：

使用v1和v2这两个值来分别计算版本号每个被'.'分割的块的版本号的大小，如果不相等，则进行比较

算法流程：

1、初始化双指针v1,v2分别为0

2、分别对两个版本字符串进行遍历

1、遍历第一个版本字符串(索引 i)，以 ‘.’ 为分割点（循环结束条件），计算每一块的版本号大小，记为 V1；

2、遍历第二个版本字符串(索引 j)，以 ‘.’ 为分割点（循环结束条件），计算每一块的版本号大小，记为 V2；

    3、对比V1, V2
        1、 $V1 == V2$ ：继续遍历两个版本字符串 $i = i + 1$ , $j = j + 1$
        2、 $V1 > V2$ ：直接返回 1
        3、 $V1 < V2$ ：直接返回 -1

图解：

代码展示：

JAVA版本

import java.util.*;
public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 比较版本号
     * @param version1 string字符串 
     * @param version2 string字符串 
     * @return int整型
     */
    public int compare (String version1, String version2) {
        // write code here
        // 两个字符串的长度
        int n = version1.length(), m = version2.length();
        // 遍历索引
        int i = 0;
        int j = 0;
        // 循环条件
        while (i < n || j < m) {
            // 用v1,v2来计算每一个块中版本号的大小
            int v1 = 0;
            int v2 = 0;
            // 若当前的字符不是分隔符，则计算字符的大小
            while (i < n && version1.charAt(i) != '.') {
                v1 = v1 * 10 + version1.charAt(i) - '0';
                i++;
            }
            // 同理计算 第二个版本号的字符大小
            while (j < m && version2.charAt(j) != '.') {
                v2 = v2 * 10 + version2.charAt(j) - '0';
                j++;
            }
            // 判断当前块中的版本号是否一致（）
            if (v1 != v2) {
                if (v1 > v2) {
                    return 1;
                }
                return -1;
            }
            // 跳过分隔符
            i++;
            j++;
        }
        // 全部比较完了，没有不等的则返回0
        return 0;
    }
}

复杂度分析

时间复杂度 $O(max(N,M))$ 。其中 $N$ 和 $M$ 指的是输入字符串的长度。遍历版本字符串时间 $O(max(N,M))$

空间复杂的 $O(1)$ ：使用双指针及其他常数级空间变量