合并两个有序数组 - 双指针算法详解

可以使用双指针的方法来解决这个问题。\n\n首先，我们初始化两个指针，分别指向 nums1 和 nums2 的末尾。然后，我们从 nums1 的末尾开始，依次比较 nums1 和 nums2 的元素大小，并将较大的元素放入 nums1 的末尾。然后，将指针向前移动一位。重复这个过程，直到将 nums2 中的所有元素都放入 nums1 中。\n\n具体的实现步骤如下：\n\n1. 初始化两个指针 p1 和 p2，分别指向 nums1 的 m-1 位置和 nums2 的 n-1 位置。\n2. 初始化一个指针 p，指向 nums1 的 m+n-1 位置。\n3. 从 p1 和 p2 开始，比较 nums1[p1] 和 nums2[p2] 的大小。\n - 如果 nums1[p1] 大于 nums2[p2]，将 nums1[p1] 放入 nums1[p] 的位置，并将 p1 向前移动一位。\n - 如果 nums1[p1] 小于等于 nums2[p2]，将 nums2[p2] 放入 nums1[p] 的位置，并将 p2 向前移动一位。\n4. 将 p 向前移动一位。\n5. 重复步骤 3 和 4，直到 p1 或 p2 小于 0。\n6. 如果 p1 小于 0，说明 nums1 中的元素已经都放入了正确的位置，只需要将 nums2 中剩下的元素放入 nums1 中。\n - 将 nums2 中剩下的元素从位置 p2 开始，依次放入 nums1 中，直到 p2 大于等于 0。\n7. 如果 p2 小于 0，说明 nums2 中的元素已经都放入了正确的位置，nums1 中的元素不需要做处理。\n\n最后，nums1 中的元素就是合并后的有序数组。\n\n以下是具体的实现代码：\n\npython\ndef merge(nums1, m, nums2, n):\n p1 = m - 1\n p2 = n - 1\n p = m + n - 1\n \n while p1 >= 0 and p2 >= 0:\n if nums1[p1] > nums2[p2]:\n nums1[p] = nums1[p1]\n p1 -= 1\n else:\n nums1[p] = nums2[p2]\n p2 -= 1\n p -= 1\n \n while p2 >= 0:\n nums1[p] = nums2[p2]\n p2 -= 1\n p -= 1\n\n\n使用示例：\n\npython\nnums1 = [1,2,3,0,0,0]\nm = 3\nnums2 = [2,5,6]\nn = 3\n\nmerge(nums1, m, nums2, n)\nprint(nums1) # 输出 [1, 2, 2, 3, 5, 6]\n