88. 合并两个有序数组【LeetCode 刷题日记】

记录自己从零开始刷 LeetCode，提高自己的数据结构与算法能力，为了获得更好的工作机会

数组 简单

题目：88. 合并两个有序数组
地址：https://leetcode.cn/problems/merge-sorted-array/description/?envType=study-plan-v2&envId=top-interview-150

解题情况

• 自己思考后，有一点思路尝试解决，没想到最优解法，希望通过暴力解法，双重 for 循环解答，但是还是没解对

参考优秀题解

方法一：先合并再排序

• 时间复杂度：O((m + n)log(m + n))
• 空间复杂度：O(1)

var merge = function (nums1, m, nums2, n) {
  // 1. 将 nums2 合并至 num1 末尾
  nums1.splice(m, nums1.length - m, ...nums2);

  // 2. 将新 num1 利用 sort 排序
  nums1.sort((a, b) => a - b);
};

方法二：双指针

• 时间复杂度：O(m + n)
• 空间复杂度：O(m + n)

var merge = function (nums1, m, nums2, n) {
  let p1 = 0,
    p2 = 0;
  let _list = 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++];
    }

    _list[p1 + p2 - 1] = cur;
  }

  for (let i = 0; i < m + n; i++) {
    nums1[i] = _list[i];
  }
};

方法三：逆向双指针

• 时间复杂度：O(m + n)
• 空间复杂度：O(1)

var merge = function (nums1, m, nums2, n) {
  let p1 = m - 1,
    p2 = n - 1;
  let tail = m + n - 1;
  let cur;

  while (p1 >= 0 || p2 >= 0) {
    if (p1 === -1) {
      cur = nums2[p2--];
    } else if (p2 === -1) {
      cur = nums1[p1--];
    } else if (nums1[p1] > nums2[p2]) {
      cur = nums1[p1--];
    } else {
      cur = nums2[p2--];
    }
    nums1[tail--] = cur;
  }
};

复盘

• 我确实算法思想很差，看到题目后自己没有什么思路
• 然后 splice 和 sort 用法我也不是很熟悉，必须要掌握一下。以前都是经常查资料，然后复制粘贴，感觉动脑子太少了，需要调整改进
• 像双指针和逆指针这样的东西我以前真的接触的很少，基本没听过，导致自己一点思路都没有
• 这些算法用 while 循环感觉比 for 多，当循环是指导终止条件的时候用 while，知道循环次数用 for 循环
• 而且这是我练习的第 2 道 LeetCode 题目，我都感觉到我对时间复杂度和空间复杂度的计算有了一些概念
• 确实刷题的过程中，多借鉴别人优秀的解法是很有帮助的，继续加油