NC104 比较版本号

1. 分割为数组再比较

考虑到题目给出的是两个string， 而比较的是小数点中间的数字大小，所以可以按照"."将字符串切割成int数组，如图所示：

图片说明

切割后，两个数组的长度可能不等，因此需要把较短的数组用0补齐，再逐位比较即可。

需要注意的实现细节：

  • 本题不需要考虑前导0， 因此1.0和1.0000是一样的，如果不是点，只需从左到右枚举数字即可，每轮迭代做*10即可，前导0不受影响。
  • 循环退出时，还剩余一个版本号。
  • C++语言中没有split，需要自己手写，java、python等可以自己手写，也可使用库函数。 
class Solution {
public:
    // 自己写的split，用于将版本号切割
    vector<int> split(string s) {
        int n = s.size(), ver = 0; // ver记录当前版本号
        vector<int> res;
        for (int i = 0; i < n; i++) {
            if (s[i] == '.') // 遇到点时，结果数组加入当前版本号，下一个版本号从0开始
                res.push_back(ver), ver = 0;
            else
                ver = ver*10 + (s[i]-'0');
        }
        // 循环退出时，还剩余一个版本号，加入之
        res.push_back(ver);
        return res;
    }


    // 符号函数
    int sgn(int a, int b) {
        if (a>b) return 1;
        else if (a<b) return -1;
        return 0;
    }

    int compare(string version1, string version2) {
        vector<int> a = split(version1), b = split(version2);

        int la = a.size(), lb = b.size();

        // 短的那个数组，在后面以0补齐
        for (int i = min(la, lb); i < max(la, lb); i++) {
            if (la < lb) a.push_back(0), la++;
            else if (la > lb) b.push_back(0), lb++;
        }

        // 此时la==lb，所以选一个就可以，且不会越界
        for (int i = 0; i < la; i++) {
            int v1 = a[i], v2 = b[i];

            // 如果比较出不一样的，就返回较大的
            if (v1 != v2) {
                return sgn(v1, v2);
            }
        }

        // 否则完全一样
        return 0;
    }
};
  • 时间复杂度：设两个字符串长度分别为n1, n2, 因为分别都要遍历一次，故总的时间复杂度为O(n1+n2).
  • 空间复杂度：O(n1+n2), 因为定义了两个数组a和b，其长度分别正比于n1和n2

2. 双指针法

思路一虽然简洁，但是存在两个优化点：

  • 时间上，对两个串各遍历了两次，是否可以优化到1次？
  • 空间上，开了n1+n2级别的空间，是否可以优化为O(1)?

我们可以使用两个指针，沿着两个字符串就地移动，每次分别跑出一个数字，即为当前待比较的版本数字（类似上图中的一个方块），如果两个“方块”中的数字不同，就可以比较出区别，否则指针同时移动，计算下一组块，直到字符串遍历完毕，如果块数不同，直接和0比较即可(这里实现时，直接定义每一块的默认值为0即可）。

class Solution {
public:

    // 符号函数
    int sgn(int a, int b) {
        if (a>b) return 1;
        else if (a<b) return -1;
        return 0;
    }

    int compare(string version1, string version2) {
        int i = 0, j = 0; // 凉指针同时从字符串开头处开始
        int l1 = version1.size(), l2 = version2.size();

        int v1 = 0, v2 = 0; // 两个方块的默认值均为0

        // 两个字符串均未跑完
        while (i < l1 || j < l2) {
            // 计算串1的当前块，如果字符串已经遍历完则什么也不做，用默认值0代替块中数据
            // 遇到点就跳出循环
            while (i < l1 && version1[i] != '.')
                v1 = v1*10 + (version1[i++] - '0');

            // 串2同理
            while (j < l2 && version2[j] != '.')
                v2 = v2*10 + (version2[j++] - '0');

            // 如果两个块中的数不一样，直接返回
            if (v1 != v2) return sgn(v1, v2);
            v1 = v2 = 0; // 恢复默认值
            i++, j++;    // 此时i和j要么出去了，要么遇到了点，跳过，出去了也无所谓
        }

        // 跑完所有块还未分出大小，就是一样
        return 0;
    }
};
  • 时间复杂度：O(max(n1, n2)), 因为两个字符串只要较长的遍历完, 另一个就不在遍历, 而是用0填充,所以时间复杂度是两个字符串中较大的一个。
  • 空间复杂度：O(1), 只有常数个变量。