题目

描述

• 牛客项目发布项目版本时会有版本号，比如1.02.11，2.14.4等等
  现在给你2个版本号version1和version2，请你比较他们的大小
  版本号是由修订号组成，修订号与修订号之间由一个"."连接。1个修订号可能有多位数字组成，修订号可能包含前导0，且是合法的。例如，1.02.11，0.1，0.2都是合法的版本号
  每个版本号至少包含1个修订号。
  修订号从左到右编号，下标从0开始，最左边的修订号下标为0，下一个修订号下标为1，以此类推。

• 比较规则：
  一. 比较版本号时，请按从左到右的顺序依次比较它们的修订号。比较修订号时，只需比较忽略任何前导零后的整数值。比如"0.1"和"0.01"的版本号是相等的
  二. 如果版本号没有指定某个下标处的修订号，则该修订号视为0。例如，"1.1"的版本号小于"1.1.1"。因为"1.1"的版本号相当于"1.1.0"，第3位修订号的下标为0，小于1
  三. version1 > version2 返回1，如果 version1 < version2 返回-1，不然返回0.

方法一

思路

比较版本号，类似于比较ip地址，很容易想到依据“.”进行字符串分割，接着将分割出的字符串转换成整数进行比较。

具体步骤

• 1.建立两个字符数组，将两个版本号分割成字符串数组存储在建立的两个字符串数组中；

• 2.遍历数组，比较对应位置的数据大小；

• 3.若是两个数组长度不同，且一个数组遍历完后，均是相等，则继续遍历剩下的数组。

• 代码如下：

  import java.util.*;
  public class Solution {
  /**
  * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
  *
  * 比较版本号
  * @param version1 string字符串 
  * @param version2 string字符串 
  * @return int整型
  */
  public int compare (String version1, String version2) {
     // 依据 . 分割字符串
     String[] numStr1 = version1.split("\\.");
     String[] numStr2 = version2.split("\\.");
  
     int i = 0;
     // 遍历数组，比较相应位置的大小
     for (; i < numStr1.length; ++i){
         int num1 = Integer.valueOf(numStr1[i]);
         if (i >= numStr2.length){
             break;
         }
         int num2 = Integer.valueOf(numStr2[i]);
         if (num2 < num1){
             return 1;
         }
         if (num2 > num1){
             return -1;
         }
     }
     // str2多的部分是否为0，不为0，则version2大
     if ( i < numStr2.length){
         while(i < numStr2.length){
             if (Integer.valueOf(numStr2[i]) != 0){
                 return -1;
             }
             ++i;
         }
     }
     // str1多的部分是否为0，不为0，则version1大
     if (i < numStr1.length){
         while(i < numStr1.length){
             if (Integer.valueOf(numStr1[i]) != 0){
                 return 1;
             }
             ++i;
         }
     }
     // 相等
     return 0;
  }
  }

• 时间复杂度：，遍历两个字符串，所以时间复杂度为其中最大的；

• 空间复杂度：，存储两个version版本。

  方法二

  思路

• 由于方法一需要额外的辅助空间来辅助计算，所以考虑使用双指针，在遍历版本号字符串时，直接进行数据大小的比较，即边分割边比较。“abc”转换成整数的公式是：a*100+b*10+c,所以在指针行进过程中，只需将原数乘以10+新遍历的数即可。

  具体步骤

• 参考下图的例子：
  
  

• 代码如下：

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 比较版本号
     * @param version1 string字符串 
     * @param version2 string字符串 
     * @return int整型
     */
    public int compare (String version1, String version2) {
        // 双指针
        int index1 = 0;
        int index2 = 0;
        // 循环遍历
        while(index1 < version1.length() 
              || index2 < version2.length()){
            int num1 = 0;
            int num2 = 0;
            // 依据"."进行分割
            while (index1 < version1.length() && 
                   version1.charAt(index1) != '.'){
                num1 = num1*10 + (version1.charAt(index1++) - '0');
            }
            // 依据"."进行分割
            while (index2 < version2.length() && 
                   version2.charAt(index2) != '.'){
                num2 = num2*10 + (version2.charAt(index2++) - '0');
            }
            if (num1 < num2){
                return -1;
            }
            if (num1 > num2){
                return 1; 
            }
            ++index1;
            ++index2;
        }

        // 相等
        return 0;
    }
}

• 时间复杂度：，遍历两个字符串，所以时间复杂度为其中最大的；
• 空间复杂度：常数级空间复杂度。