/*
 * @lc app=leetcode.cn id=88 lang=javascript
 *
 * [88] 合并两个有序数组
 */

// @lc code=start
/**
 * @param {number[]} nums1
 * @param {number} m
 * @param {number[]} nums2
 * @param {number} n
 * @return {void} Do not return anything, modify nums1 in-place instead.
 */
var merge = function (nums1, m, nums2, n) {
  // 1. 借助一个临时数组
  // let arr = []
  // let i = 0, j = 0;
  // while (arr.length < m + n) {
  //   if (j >= n) {
  //     arr = arr.concat(nums1.slice(i, m))
  //   } else if (i >= m) {
  //     arr = arr.concat(nums2.slice(j, n))
  //   } else if (nums1[i] <= nums2[j]) {
  //     arr.push(nums1[i++]);
  //   } else {
  //     arr.push(nums2[j++])
  //   }
  // }

  // for (let i = 0; i < arr.length; i++) {
  //   nums1[i] = arr[i]
  // }

  // 2. 借助nums1后面的空间
  let len = m + n - 1
  let p1 = m - 1, p2 = n - 1;
  let cur;
  while (p1 >= 0 || p2 >= 0) {
    if (p2 === -1) {
      cur = nums1[p1--]
    } else if (p1 === -1) {
      cur = nums2[p2--]
    } else if (nums1[p1] > nums2[p2]) {
      cur = nums1[p1--]
    } else {
      cur = nums2[p2--]
    }
    nums1[len--] = cur
  }
};
// @lc code=end

console.log(merge([1, 2, 3, 0, 0, 0], 3, [2, 5, 6], 3))
console.log(merge([4, 5, 6, 0, 0, 0], 3, [1, 2, 3], 3))
console.log(merge([1, 2, 3, 0, 0, 0], 3, [2, 5, 6], 3))
console.log(merge([1, 2, 4, 5, 6, 0], 5, [3], 1))