88、合并两个有序数组

;(function () {
  /**
     * 给你两个按 非递减顺序 排列的整数数组 nums1 和 nums2，另有两个整数 m 和 n ，分别表示 nums1 和 nums2 中的元素数目。
     * 请你 合并 nums2 到 nums1 中，使合并后的数组同样按 非递减顺序 排列。
     * 注意：最终，合并后数组不应由函数返回，而是存储在数组 nums1 中。为了应对这种情况，nums1 的初始长度为 m + n，其中前 m 个元素表示应合并的元素，后 n 个元素为 0 ，应忽略。nums2 的长度为 n 。
     Do not return anything, modify nums1 in-place instead.
     */
  function merge(nums1: number[], m: number, nums2: number[], n: number): void {
    // 方法一
    // nums2.forEach((x, k) => {
    //     k < n ? nums1[m+k] = x : null;
    // })
    // nums1.sort((a, b) => a - b)

    // 方法二
    // for (let i = 0; i < nums2.length; i++) {
    //     if ( i < n) {
    //         nums1[m+i] = nums2[i]
    //     } else {
    //         break;
    //     }
    // }
    // nums1.sort((a, b) => a - b)

    // 方法三：双指针
    let p1 = 0,
      p2 = 0
    let sortedArr = new Array(m + n).fill(0)
    let cur
    while (p1 < m || p2 < n) {
      if (p1 === m) {
        cur = nums2[p2++]
      } else if (p2 === n) {
        cur = nums1[p1++]
      } else if (nums1[p1] < nums2[p2]) {
        cur = nums1[p1++]
      } else {
        cur = nums2[p2++]
      }
      sortedArr[p1 + p2 - 1] = cur
    }
    for (let i = 0; i < sortedArr.length; i++) {
      nums1[i] = sortedArr[i]
    }
  }
  let nums1 = [1, 2, 3, 0, 0, 0]
  let nums2 = [2, 5, 6]
  let m = 3
  let n = 3
  merge(nums1, m, nums2, n)
  console.log('Res: ', nums1)

  // let arr1 = [-10,-10,-9,-9,-9,-8,-8,-7,-7,-7,-6,-6,-6,-6,-6,-6,-6,-5,-5,-5,-4,-4,-4,-3,-3,-2,-2,-1,-1,0,1,1,1,2,2,2,3,3,3,4,5,5,6,6,6,6,7,7,7,7,8,9,9,9,9,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0]
  // let a = 55
  // let arr2 = [-10,-10,-9,-9,-9,-9,-8,-8,-8,-8,-8,-7,-7,-7,-7,-7,-7,-7,-7,-6,-6,-6,-6,-5,-5,-5,-5,-5,-4,-4,-4,-4,-4,-3,-3,-3,-2,-2,-2,-2,-2,-2,-2,-1,-1,-1,0,0,0,0,0,1,1,1,2,2,2,2,2,2,2,2,3,3,3,3,4,4,4,4,4,4,4,5,5,5,5,5,5,6,6,6,6,6,7,7,7,7,7,7,7,8,8,8,8,9,9,9,9]
  // let b = 99
  // merge(arr1, a, arr2, b)
  // console.log('Res: ', arr1)
})()