Leetcode 合并两个数组

算法思想是双指针从后往前合并，利用了 nums1 数组的尾部空间来存储合并后的结果，从而避免了额外空间的使用。具体步骤如下：

1. 初始化指针：

   • i 指向 nums1 的有效元素末尾，即位置 m - 1。
   • j 指向 nums2 的末尾，即位置 n - 1。
   • k 指向 nums1 的最后一个位置，即 m + n - 1，这是合并后数组的尾部位置。

2. 从尾部开始比较和填充：

   • 使用 while 循环从后往前遍历，比较 nums1[i] 和 nums2[j] 的大小。
   • 如果 nums1[i] 大于 nums2[j]，将 nums1[i] 的值赋给 nums1[k]，然后将指针 i 和 k 分别左移（递减）。
   • 如果 nums2[j] 大于等于 nums1[i]，则将 nums2[j] 的值赋给 nums1[k]，然后将指针 j 和 k 左移。
   • 这个过程不断将较大的元素放到 nums1 的后部，从而保证结果是非递减排序的。

3. 处理剩余的 nums2 元素：

   • 当 nums1 的元素已经全部比较完后（即 i < 0），如果 nums2 中还有剩余元素（即 j >= 0），则将 nums2 中剩下的所有元素直接复制到 nums1 的开头部分。因为 nums2 本身是有序的，所以直接复制即可。

4. 时间复杂度和空间复杂度：

   • 该算法的时间复杂度为 (O(m + n))，因为每个元素只被遍历一次。
   • 空间复杂度为 (O(1))，因为在 nums1 上原地进行合并操作，没有使用额外空间。

这样设计的好处是利用了 nums1 的后半部分空间，避免了新数组的创建，节省了空间。

java 代码

class Solution {public void merge(int[] nums1, int m, int[] nums2, int n) {int i = m - 1;int j = n - 1;int k = m + n - 1;while(i >= 0 && j >= 0) {if(nums1[i] > nums2[j]) {nums1[k--] = nums1[i--];}else {nums1[k--] = nums2[j--];}}while(j >= 0) {nums1[k--] = nums2[j--];}}
}

为什么在第一个while循环结束后，只由nums2有可能仍然还有剩余元素，而不可能是nums1?

在第一个 while 循环结束后，只有 nums2 有可能仍然有剩余元素，而 nums1 不会有剩余的未处理元素，这是因为 nums1 中前 m 个元素已经在数组 nums1 的末尾进行了预留，并且 nums1 的后半部分已被填充为 0，这些 0 的位置就是为了腾出空间来合并 nums2 的元素。

具体原因如下：

1. 预留空间的设计：题目要求将 nums2 的元素合并到 nums1 中。nums1 的数组长度是 m + n，其中前 m 个位置是 nums1 的有效元素，后 n 个位置是用来放 nums2 的元素的空间（这些位置最初被填充为 0）。因此，从逻辑上讲，nums1 的所有有效元素在一开始就已经包含在数组的前 m 个位置上。

2. 从后向前合并的策略：代码中使用了从后向前合并的策略，即从 nums1 和 nums2 的末尾元素开始逐个比较，将较大的元素放到 nums1 的最后位置（k = m + n - 1），依次向前填充。因此，在合并过程中，nums1 的所有有效元素要么已经被比较并放置在正确的位置，要么在 while 循环结束时已经全部处理完。

3. 可能剩余的情况：如果 nums2 的元素较小（即 nums2 中的元素比 nums1 中的剩余元素更小），则 nums2 中可能会有未处理的元素。这是因为 while 循环中的条件是 i >= 0 && j >= 0，一旦 i < 0（即 nums1 的有效元素已经处理完），while 循环结束，接下来只需要将 nums2 中剩下的元素（如果有）放到 nums1 的前部位置即可。

4. 剩余的处理方式：当 nums1 的有效元素都已处理完（即 i < 0），但 nums2 中还有未处理的元素（j >= 0），这些剩余的 nums2 元素是按非递减顺序排列的，因此可以直接复制到 nums1 的开头。

综上所述，在第一个 while 循环结束后，nums1 中的有效元素（前 m 个）要么已经放置到正确位置，要么已经被用来比较且完全填充到数组后部，而 nums2 中的元素如果还未处理完，则直接复制到 nums1 开头。这就是为什么第一个 while 循环结束后只可能有 nums2 中的元素剩余。