88. 合并两个有序数组

[buuing]

给你两个有序整数数组 nums1 和 nums2，请你将 nums2 合并到 nums1 中，使 nums1 成为一个有序数组。

说明：

• 初始化 nums1 和 nums2 的元素数量分别为 m 和 n 。
• 你可以假设 nums1 有足够的空间（空间大小大于或等于 m + n）来保存 nums2 中的元素。

示例：

输入：
nums1 = [1,2,3,0,0,0], m = 3
nums2 = [2,5,6],       n = 3

输出：[1,2,2,3,5,6]

提示：

• -10^9 <= nums1[i], nums2[i] <= 10^9
• nums1.length == m + n
• nums2.length == n

来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/merge-sorted-array 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

---

• 双指针 - 从后向前

思路: 开局先让m和n各自减1, 因为数组索引是从0开始的, 然后索引i用来从后向前遍历nums1

! 第一次循环
     m=2
[1,2,3,0,0,0] i=5
[0,5,6]
     n=2
! 因为nums1[2]<nums2[2], 所以nums1[i] = nums2[n], i--, n--

! 第二次循环
     m=2
[1,2,3,0,0,6] i=4
[0,5,6]
   n=1
! 此时nums1[2]<nums2[1], 所以nums1[i] = nums2[n], i--, n--

! 第三次循环
     m=2
[1,2,3,0,5,6] i=3
[0,5,6]
 n=0
! 此时nums1[2]>nums2[0], 所以nums1[i] = nums1[m], i--, m--

! 第四次循环
   m=1
[1,2,3,3,5,6] i=2
[0,5,6]
 n=0
! 此时nums1[1]>nums2[0], 所以nums1[i] = nums1[m], i--, m--

! 第五次循环
 m=0
[1,2,2,3,5,6] i=1
[0,5,6]
 n=0
! 此时nums1[0]>nums2[0], 所以nums1[i] = nums1[m], i--, m--

! 第六次循环
m=-1
[1,1,2,3,5,6] i=0
[0,5,6]
 n=0
! 此时nums1[m]和nums2[n]进行比较
- 到了这里最后一次循环的时候, 要么m=-1, 要么n=-1
- 那我们可以让n>=0来成为while循环的条件
- 当n=-1的说明nums1[0]的位置是正确的, 此时也就无需进行调整, 结束循环即可
- 当m = -1的时候, nums2[-1]会得到一个undefined, undefined跟数字进行比较的时候, 会转换成NaN
- NaN (Not a Number) 跟任何数字进行比较的时候, 都会得到一个 false, 也就意味着必定进入else
- 那我们正好可以把nums2[0]的值赋给nums1[0], 然后正好结束循环

! 推理结束, n 变成 -1 结束循环
[0,1,2,3,5,6]

代码

const merge = (nums1, m, nums2, n) => {
  let i = nums1.length - 1
  m--
  n--
  while (n >= 0) {
    if (nums1[m] > nums2[n]) {
      nums1[i--] = nums1[m--]
    } else {
      nums1[i--] = nums2[n--]
    }
  }
}

[zhonghuidong94]

都用上[n--] 哪就上三元吧，代码更少了😊

var merge = function(nums1, m, nums2, n) {
    // 都处理为索引
    let maxIndex = m + n - 1;
    m--;
    n--;
    
    while(n > -1) {
        // 从右向左 向 nums1[maxIndex] 赋值,  取 nums1[m] 、 nums2[n] 最大的
        nums1[maxIndex--]  = nums1[m] > nums2[n] ? nums1[m--] : nums2[n--];

    }
    return nums1;
};

[buuing]

@zhonghuidong94

只是感觉用 if...else 的话, 结构上会比较清晰, 因为代码毕竟是给人读的

所以我会选择牺牲一些性能提升微弱的地方, 来追求代码的可读性

[mingnang]

有道理，我懂了