第155题 手写合并两个递增数组

    var arr1 = [1,3,5,7,9]
    var arr2 = [2,4,6,8]
    
    // 1.直接用concat+sort 时间复杂度较高，因为有排序，复杂度至少是O(n*logn)
    var res1 = arr1.concat(arr2).sort((a,b)=>a-b)
    console.log(res1)
    
    // 2.使用双指针，时间复杂度 O(m + n) => O(n)
    var res = []
    var i = 0
    var j = 0
    
    // 只要arr1和arr2还有值继续循环
    while(arr1[i] !== null || arr2[j] !== null) {
      const v1 = arr1[i]
      const v2 = arr2[j]
    
      if(v1 == null && v2 == null) {
        // v1 v2都没有值了 停止
        break;
      }
    
      if(v1 < v2 || v2 == null) {
        // v1较小则只拼接v1
        res.push(v1)
        i++
      }
      if(v1 > v2 || v1 == null) {
        // v2较小则只拼接v2
        res.push(v2)
        j++
      }
      if(v1 === v2) {
        // v1、v2相等
        res.push(v1)
        i++
        res.push(v2)
        j++
      }
    }
    
    console.log(res) // [1,2,3,4,5,6,7,8,9]