一道腾讯面试题竟引发我与好友两人争执不下

事情经过

下班坐地铁的时候，好友突然给我发过来一条微信：

这道题是这样：

咱们软件开发不是经常不是有版本号吗？

比如经典的兼容IE浏览器的 jQuery1.x 最后的一个版本1.12.4，但有时咱们又不会精确到第三位，比如：vue3.0、react16.8…

然后实现一个方法，把两个版本号传进去，可以两位( 如：3.0 )也可以三位( 如：1.12.4 )，如果第一个版本比第二个版本大，就返回1。

如果第二个版本比第一个大，就返回-1。 其他情况返回0。

我很快就想出了一个思路：( 先省略前期的各种判断以及类型转换 )用split方法将其切割成数组，然后把两个数组的第一位相比较，如果第一位就比较出结果就可以直接返回，没有必要在比较第二位了，依此类推，直到比较到最后一位。如果比较到最后一位的时候两个数组的长度不一致，就为短的那一方加个0，比如3.0就会变成3.0.0。

本以为他也会这么想，但万万没想到他说出了一个脑回路跟我不太一样的解法：

他这么一说，我一下子就想到了JS小数计算不准确的问题，他肯定是从那获得的灵感。

不过他居然说我是暴力解法，我怎么觉得他那种才是暴力解法……

既然有争议，那咱们就一不做二不休，实现一下吧！

我的split方法

function comparison (version1, version2) {
  // 参数的类型
  const types = ['string', 'number']

  // 第一个参数的类型
  const type1 = typeof version1

  // 第二个参数的类型
  const type2 = typeof version2
  
  // 参数不是字符串或数字的情况下返回0
  if (!types.includes(type1) || !types.includes(type2)) return 0

  // 如果version1是number就将其转成字符串
  const ver1 = type1 === 'number' ? version1.toString() : version1

  // 如果version2是number就将其转成字符串
  const ver2 = type2 == 'number' ? version2.toString() : version2

  // 将version1变成数组
  const versionArr1 = ver1.split('.')

  // 将version2变成数组
  const versionArr2 = ver2.split('.')

  // 获取长度最长的数组的length
  const len = Math.max(versionArr1.length, versionArr2.length)

  // 循环对比版本号，如果前一位比较不出大小就继续向后对比
  for (let i = 0; i < len; i++) {
    // 如果长度不一致将自动补0 同时将字符串转为数字
    const version1 = Number(versionArr1[i]) || 0
    const version2 = Number(versionArr2[i]) || 0

    if (version1 > version2) {
      // 如果version1大就返回1
      return 1
    } else if (version1 < version2) {
      // 如果version2大就返回-1
      return -1
    } else {
      // 如果比较到最后就返回0，否则继续比较
      if (i + 1 === len) {
        return 0
      } else {
        continue
      }
    }
  }
}

为了方便观看这里省略了用正则判断传进来的参数是否符合xx.xx.xx形式或者去除前面的0等一些繁琐判断( 面试题应该也不用写那么细，写出思路即可 )，所以只判断了参数是否为string或number类型，来测试一下：

由于没有写死判断，所以甚至可以实现无限版本号的比较：

好像没啥毛病哈，反正面试题说的是其余情况返回0，版本相等、传错参数应该都属于其余情况。

当然这个版本号过多( 1.2.3.4.5.6 )的情况严格意义上也算是传错参数，但为了验证一下版本号过多的情况我的方法性能与朋友的方法性能哪个好( 验证一下是否为暴力解法 )，所以写成了这样( 这种更难写呢 )，而且写成这样更利于可持续化发展嘛，如果较真的朋友可以采用if(len === 2)和if(len === 3)的这种形式来解题。

接下来咱们再来看一下我朋友的方法:

朋友的replace方法

经测试有bug，后来又改了几版，下面是最终版：

function compareVersion(version1, version2) {
      let ver1 = version1.split('.')
      let ver2 = version2.split('.')
      let len1 = ''
      let len2 = ''
      ver1.forEach((item,index)=>{
        let zero = ''
        for (let i = 0; i < index; i++) {
          zero += '0'
        }
        len1 += zero + item
      })
      ver2.forEach((item,index)=>{
        let zero = ''
        for (let i = 0; i < index; i++) {
          zero += '0'
        }
        len2 += zero + item
      })
      let len = len1.length - len2.length
      if(len > 0){
        len2 = Number(len2) * Math.pow(10,Math.abs(len))
      }else{
        len1 = Number(len1) * Math.pow(10,Math.abs(len))
      }
      if(len1>len2){
        return 1
      }else if(len1<len2){
        return -1
      }else{
        return 0
      } 
}

<center>（最终版其实没有用到replace方法，他也用了split）</center>

这是他的原代码，没有写注释，后来他发微信过来说让我把循环加0的那步去掉，只加一个0即可。

刚好我打算改造一下他的代码顺便整理下格式然后加点注释，改造后如下：

function compareVersion(version1, version2) {
      // 将传进的版本号切割为数组
      const ver1 = version1.split('.')
      const ver2 = version2.split('.')

      // 将数组相加中间补0最后变成一个数字(字符串)
      let len1 = ver1.reduce((sum, item) => sum + '0' + item, '')
      let len2 = ver2.reduce((sum, item) => sum + '0' + item, '')

      // 得出两个数字(字符串)长度的差值
      const len = len1.length - len2.length

      // 如果差值大于0
      if (len > 0) {
        // 第二个数字就乘以十的差值次方
        len2 = Number(len2) * Math.pow(10, Math.abs(len))
      } else {
        // 否则第一个数字就乘以十的差值次方
        len1 = Number(len1) * Math.pow(10, Math.abs(len))
      }

      if (len1 > len2) {
        // 如果第一个数比第二个数大，返回1
        return 1
      } else if (len1 < len2) {
        // 如果第一个数比第二个数小，返回-1
        return -1
      } else {
        // 否则返回0
        return 0
      } 
}

由于没做判断，导致传入别的值会报错，不过在传参正确的情况下好像没什么毛病。

然后今早我们又争执了一番：

我是这么想的，他这个方法无论第一位是否相同，都是要循环整个数组的。

而我的只要第一位不一样瞬间就能得出结果，然后还说我的算法复杂度是O(n)，我就想不明白了一个for循环遍历数组怎么就成O(n)了，咱们程序里循环遍历数组多普遍的一件事啊，都成O(n)了？

而且如果不算前期判断传入的参数是否为数组中的类型的话，我只循环了一次数组，他这个循环两个数组，我说他肯定不服，那咱们用数据说话：

运行时长

首先在方法的第一行就加入一个 console.time('运行时长：') ，然后再在返回值之前加入 console.timeEnd('运行时长：') 。

这是一个比较方便的测试程序运行时长的一种方式，注意 console.time() 和 console.timeEnd() 里面的参数一定要一模一样才管用，大家可以去试试。

我的代码：

function comparison (version1, version2) {
  console.time('运行时长：')
  // 参数的类型
  const types = ['string', 'number']

  // 第一个参数的类型
  const type1 = typeof version1

  // 第二个参数的类型
  const type2 = typeof version2
  
  // 参数不是字符串或数字的情况下返回0
  if (!types.includes(type1) || !types.includes(type2)) return 0

  // 如果version1是number就将其转成字符串
  const ver1 = type1 === 'number' ? version1.toString() : version1

  // 如果version2是number就将其转成字符串
  const ver2 = type2 == 'number' ? version2.toString() : version2

  // 将version1变成数组
  const versionArr1 = ver1.split('.')

  // 将version2变成数组
  const versionArr2 = ver2.split('.')

  // 获取长度最长的数组的length
  const len = Math.max(versionArr1.length, versionArr2.length)

  // 循环对比版本号，如果前一位比较不出大小就继续向后对比
  for (let i = 0; i < len; i++) {
    // 如果长度不一致将自动补0 同时将字符串转为数字
    const version1 = Number(versionArr1[i]) || 0
    const version2 = Number(versionArr2[i]) || 0

    if (version1 > version2) {
      console.timeEnd('运行时长：')  
      // 如果version1大就返回1
      return 1
    } else if (version1 < version2) {
      console.timeEnd('运行时长：')
      // 如果version2大就返回-1
      return -1
    } else {
      // 如果比较到最后就返回0，否则继续比较
      if (i + 1 === len) {
        console.timeEnd('运行时长：')
        return 0
      } else {
        continue
      }
    }
  }
}

他的代码：

function compareVersion(version1, version2) {
      console.time('运行时长：')  
      // 将传进的版本号切割为数组
      const ver1 = version1.split('.')
      const ver2 = version2.split('.')

      // 将数组相加中间补0最后变成一个数字(字符串)
      let len1 = ver1.reduce((sum, item) => sum + '0' + item, '')
      let len2 = ver2.reduce((sum, item) => sum + '0' + item, '')

      // 得出两个数字(字符串)长度的差值
      const len = len1.length - len2.length

      // 如果差值大于0
      if (len > 0) {
        // 第二个数字就乘以十的差值次方
        len2 = Number(len2) * Math.pow(10, Math.abs(len))
      } else {
        // 否则第一个数字就乘以十的差值次方
        len1 = Number(len1) * Math.pow(10, Math.abs(len))
      }

      if (len1 > len2) {
        console.timeEnd('运行时长：')
        // 如果第一个数比第二个数大，返回1
        return 1
      } else if (len1 < len2) {
        console.timeEnd('运行时长：')
        // 如果第一个数比第二个数小，返回-1
        return -1
      } else {
        console.timeEnd('运行时长：')
        // 否则返回0
        return 0
      } 
}

测试结果：

按理说，应该是第一位就能比较出结果，并且位数很长的一个数值，运行的差距就越明显，来试一下：

差了两倍多，不过感觉怎么没有自己想象中的差距那么明显呢？换下位置再试试：

这回差了6倍……嗯。

而且我感觉我多比他写的判断参数也耗费了不少时间，懒得改了，拿一个极端的例子再试一下：

还是数倍的差距，大家怎么看呢？有没有更好的办法实现这道题呢？