Leetcode 合并两个数组
算法思想是双指针从后往前合并，利用了 nums1 数组的尾部空间来存储合并后的结果，从而避免了额外空间的使用。具体步骤如下：
-
初始化指针：
i指向nums1的有效元素末尾，即位置m - 1。j指向nums2的末尾，即位置n - 1。k指向nums1的最后一个位置，即m + n - 1，这是合并后数组的尾部位置。
-
从尾部开始比较和填充：
- 使用
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的后部，从而保证结果是非递减排序的。
- 使用
-
处理剩余的
nums2元素：- 当
nums1的元素已经全部比较完后（即i < 0），如果nums2中还有剩余元素（即j >= 0），则将nums2中剩下的所有元素直接复制到nums1的开头部分。因为nums2本身是有序的，所以直接复制即可。
- 当
-
时间复杂度和空间复杂度：
- 该算法的时间复杂度为 (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 的元素。
具体原因如下：
-
预留空间的设计：题目要求将
nums2的元素合并到nums1中。nums1的数组长度是m + n，其中前m个位置是nums1的有效元素，后n个位置是用来放nums2的元素的空间（这些位置最初被填充为0）。因此，从逻辑上讲，nums1的所有有效元素在一开始就已经包含在数组的前m个位置上。 -
从后向前合并的策略：代码中使用了从后向前合并的策略，即从
nums1和nums2的末尾元素开始逐个比较，将较大的元素放到nums1的最后位置（k = m + n - 1），依次向前填充。因此，在合并过程中，nums1的所有有效元素要么已经被比较并放置在正确的位置，要么在while循环结束时已经全部处理完。 -
可能剩余的情况：如果
nums2的元素较小（即nums2中的元素比nums1中的剩余元素更小），则nums2中可能会有未处理的元素。这是因为while循环中的条件是i >= 0 && j >= 0，一旦i < 0（即nums1的有效元素已经处理完），while循环结束，接下来只需要将nums2中剩下的元素（如果有）放到nums1的前部位置即可。 -
剩余的处理方式：当
nums1的有效元素都已处理完（即i < 0），但nums2中还有未处理的元素（j >= 0），这些剩余的nums2元素是按非递减顺序排列的，因此可以直接复制到nums1的开头。
综上所述，在第一个 while 循环结束后，nums1 中的有效元素（前 m 个）要么已经放置到正确位置，要么已经被用来比较且完全填充到数组后部，而 nums2 中的元素如果还未处理完，则直接复制到 nums1 开头。这就是为什么第一个 while 循环结束后只可能有 nums2 中的元素剩余。