0088. Merge Sorted Array ======================== 题目信息 -------- :题号: 0088. 合并两个有序数组 :难度: Easy :主题: 数组、双指针、原地归并、逆向写入 :原题: `LeetCode 0088 `_ :重点: 从额外缓冲的正向归并,推导到利用尾部空槽逆向原地写入 题目重述 -------- 给定两个按非递减顺序排列的整数数组 ``nums1`` 和 ``nums2``,以及整数 ``m``、``n``: - ``nums1`` 的长度为 ``m + n``,其中前 ``m`` 个元素有效,后 ``n`` 个位置是预留空间; - ``nums2`` 的长度为 ``n``,全部元素有效。 把两个有效序列合并为一个非递减序列,并直接写回 ``nums1``。函数不返回合并后的数组。 ``nums1`` 尾部预留位置原有的数值只是占位内容,不属于待合并元素。 约束为 ``0 <= m, n <= 200``、``1 <= m + n <= 200``,数组元素范围为 ``[-10^9, 10^9]``。 自建示例 -------- .. code-block:: text 输入: nums1 = [1,4,7,0,0,0], m = 3 nums2 = [2,3,9], n = 3 修改后:nums1 = [1,2,3,4,7,9] 两个有效前缀依次提供元素 ``1,4,7`` 和 ``2,3,9``,末尾三个 ``0`` 只是预留空间。 .. code-block:: text 输入: nums1 = [0,0,0], m = 0 nums2 = [-2,5,8], n = 3 修改后:nums1 = [-2,5,8] 第一个有效序列为空,需要把 ``nums2`` 的全部元素写入 ``nums1``。 .. code-block:: text 输入: nums1 = [1,3,6], m = 3 nums2 = [], n = 0 修改后:nums1 = [1,3,6] 第二个序列为空时,``nums1`` 已经是最终结果。 C++ 实现 -------- .. code-block:: cpp #include #include class Solution { private: void appendAndSort(std::vector& nums1, int m, const std::vector& nums2, int n) { for (int index = 0; index < n; ++index) { nums1[m + index] = nums2[index]; } std::sort(nums1.begin(), nums1.end()); } void copyThenMergeForward(std::vector& nums1, int m, const std::vector& nums2, int n) { std::vector first(nums1.begin(), nums1.begin() + m); int first_index = 0; int second_index = 0; int write = 0; while (first_index < m && second_index < n) { if (first[first_index] <= nums2[second_index]) { nums1[write++] = first[first_index++]; } else { nums1[write++] = nums2[second_index++]; } } while (first_index < m) { nums1[write++] = first[first_index++]; } while (second_index < n) { nums1[write++] = nums2[second_index++]; } } void mergeBackward(std::vector& nums1, int m, const std::vector& nums2, int n) { int first = m - 1; int second = n - 1; int write = m + n - 1; while (second >= 0) { if (first >= 0 && nums1[first] > nums2[second]) { nums1[write] = nums1[first]; --first; } else { nums1[write] = nums2[second]; --second; } --write; } } public: void merge(std::vector& nums1, int m, std::vector& nums2, int n) { mergeBackward(nums1, m, nums2, n); } }; 题解 ---- 直接利用排序 ~~~~~~~~~~~~ 最直接的方法是把 ``nums2`` 写入 ``nums1`` 的预留区域,再对整个数组排序。这样可以得到正确结果, 但没有利用两个输入序列原本已经有序这一条件,时间为 ``O((m+n)log(m+n))``。 正向归并 ~~~~~~~~ 标准归并从两个序列的左端开始,每次取较小值写入结果。这里若直接覆盖 ``nums1[0]``,可能破坏 ``nums1`` 中尚未读取的有效元素。例如 ``nums1 = [4,7,0,0]``、``nums2 = [1,5]`` 时,先写入 1 会覆盖仍需参与比较的 4。 复制 ``nums1`` 的前 ``m`` 项后即可安全正向归并。每轮从两个未合并前缀的首元素中选较小者, 时间降为 ``O(m+n)``,代价是保存副本所需的 ``O(m)`` 额外空间。 尾部空槽 ~~~~~~~~ ``nums1`` 已在右侧预留 ``n`` 个位置。与其从左侧写最小值,不如从右侧写最大值: .. code-block:: text first = m - 1 second = n - 1 write = m + n - 1 ``first`` 和 ``second`` 分别指向两个未合并序列的最大元素,``write`` 指向当前最右空槽。 比较两个尾值后,把较大者放到 ``write``,再向左移动对应指针。 .. list-table:: :header-rows: 1 * - 未处理 nums1 - 未处理 nums2 - 本轮写入 * - ``[1,4,7]`` - ``[2,3,9]`` - 9 * - ``[1,4,7]`` - ``[2,3]`` - 7 * - ``[1,4]`` - ``[2,3]`` - 4 * - ``[1]`` - ``[2,3]`` - 3 写入不变量 ~~~~~~~~~~ 循环开始时满足: .. code-block:: text write = first + second + 1 只要 ``second >= 0``,就有 ``write > first``。因此写入位置始终严格位于 ``nums1`` 尚未读取的 有效前缀右侧,不会覆盖未来仍要比较的元素。每轮同时减少 ``write`` 和某一个读指针,这个关系持续成立。 已写入的后缀包含当前已取出的最大元素,并保持非递减顺序。继续选择两个未处理尾值中的较大者, 就能逐步把这个有序后缀向左扩展。 剩余元素 ~~~~~~~~ 主循环只要求 ``second >= 0``: - ``nums2`` 先耗尽时,``nums1`` 剩余元素已经位于结果前缀的正确位置,无需搬动; - ``nums1`` 先耗尽时,条件 ``first >= 0`` 失败,循环会继续把 ``nums2`` 的剩余元素写到前部。 相等时主实现选择 ``nums2`` 的元素写到更右侧。题目只要求数值有序,不要求两个数组之间保持稳定性, 所以选择任一侧都不影响正确性。 复杂度 ~~~~~~ 拼接后排序的时间为 ``O((m+n)log(m+n))``。复制后正向归并和尾部逆向归并的时间均为 ``O(m+n)``;前者额外使用 ``O(m)`` 空间,后者只使用三个下标,额外空间为 ``O(1)``。