网络异常，图片无法展示
|
「这是我参与2022首次更文挑战的第21天，活动详情查看：2022首次更文挑战」
给定两个排序后的数组 A 和 B，其中 A 的末端有足够的缓冲空间容纳 B。 编写一个方法，将 B 合并入 A 并排序。
初始化 A 和 B 的元素数量分别为 m 和 n。
示例:
输入: A = [1,2,3,0,0,0], m = 3 B = [2,5,6], n = 3 输出: [1,2,2,3,5,6] 复制代码
说明:
A.length == n + m
解题思路
因为输入数组 A,B都是有序的数组，所以我们在合并的过程中只要保证将数组 B 中的元素插入合适的位置，就能保证合并后的数组依然是有序的。
这里我们定义两个指针 a,b，分别指向数组 A,B 的最后一个元素。
每次让 a 向前找到第一个小于等于 b 指向元素的位置（如果初始 a 指向元素小于等于 b 指向元素，则无需移动），然后将 a 指针后面的元素统一向后移动一位，在空出的位置插入 b 指向元素。这样就保证了每次插入 B 数组中的元素都在合适的位置，插入后，数组 A 依然有序。
向前移动 b 指针，重复上述过程，直到处理完数组 B 中的所有元素，就完成了将 B 合并入 A 的过程。
动画演示
网络异常，图片无法展示
|
代码实现
var merge = function (A, m, B, n) { // 初始化指针 a 指向 A 数组的末尾元素 let a = m - 1, // 初始化指针 b 指向 B 数组的末尾元素 b = n - 1 // 从后向前的处理 B 数组中的每一个元素 while (b >= 0) { // 让 a 指向第一个小于等于 b 指向元素的位置 while (A[a] > B[b]) a-- // 将 a 指针后面的元素统一向后移动一位 move(A, a) // 将 b 指向元素插入空出的位置 A[a + 1] = B[b] // 向前移动 b 指针处理剩余元素 b-- } /* * 传入数组和指定下标，将下标后面的元素统一向后移动一位 * @param {number[]} arr * @param {number} ind * * @return {void} */ function move(arr, ind) { // 从后向前将每一个元素向后移动一位，直到指定下标为止 for (let i = arr.length - 2; i > ind; i--) { arr[i + 1] = arr[i] } } } 复制代码
至此我们就完成了 leetcode-面试题 10.01-合并排序的数组
如有任何问题或建议，欢迎留言讨论！👏🏻👏🏻👏🏻
