本文由 简悦 SimpRead 转码， 原文地址 mp.weixin.qq.com

今天来做一个经典面试题，合并两个有序数组

问题描述

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

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

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

解题思路

关键在于将两个有序数组合并为一个有序数组。由于 nums1 数组有足够的空间，我们可以从数组的末尾开始比较两个数组的元素，逐步将较大的元素写入 nums1 的末尾。

我们使用三个指针，len1 和 len2 分别指向 nums1 和 nums2 末尾的有效元素，len 指向合并后的数组末尾。该算法的时间复杂度为 O(m+n)。在合并过程中，我们从两个数组的末尾开始比较，逐步向前填充合并后的数组，确保合并后的数组仍然有序。

代码实现

这里是使用 js 写的合并两个有序数组的函数

const merge = function(nums1, m, nums2, n) {    let len1 = m - 1,        len2 = n - 1,        len = m + n - 1    while(len2 >= 0) {        if(len1 < 0) {            nums1[len--] = nums2[len2--]            continue        }        nums1[len--] = nums1[len1] >= nums2[len2]           ? nums1[len1--]          : nums2[len2--]    }    return nums1};// 调用合并函数merge([1,2,3,0,0,0], 3, [2,5,6], 3);

• nums1、nums2 有序，若把 nums2 全部合并到 nums1，则合并后的 nums1 长度为 m+n。

• 从下标 m+n-1 的位置开始填充 nums1，比较 nums1[len1] 与 nums2[len2] 的大小，将最大值写入 nums1[len]。

• 若 nums1[len1] >= nums2[len2]，则 nums1[len--] = nums1[len1--]，此处 -- 是因为写入成功后，下标自动减一，继续往前比较。

• 否则，nums1[len--] = nums2[len2--]。

• 边界条件：

• 若 len2 大于等于 0 且 len1 小于 0，此时 nums1 已全部写入， nums2 还未合并完，仅需将 nums2 的剩余元素（0…len）写入 nums2 即可，写入后合并完成。

• 若 len2 < 0，此时 nums2 已全部合并到 nums1，合并完成。

The End

感谢阅读面试系列！如果你有任何疑问或者希望了解更多算法相关的内容，请留言告诉我，我们下篇再见！

最后不要忘了点赞和在看呦！

祝 2024 年暴富！暴美！暴瘦！