代码训练(1)LeetCode之合并两个有序数组
Author: Once Day Date: 2024年3月5日
漫漫长路，才刚刚开始…
全系列文章可参考专栏: 十年代码训练_Once-Day的博客-CSDN博客
参考文章:
1. 问题
2. 分析
该问题是一个非常基础的编程题目，我们用C语言来实现，并且额外要求性能较高(速度90%，内存80%)。
首先，想象你有两排学生，他们分别按身高从矮到高排好了队。现在我们要将这两排学生合并成一排，同时保持身高从矮到高的顺序。这就像我们要合并的两个数组，分别是nums1和nums2，它们已经按照非递减顺序（即从小到大）排列好。整数m和n分别告诉我们nums1和nums2中有多少个元素是有效的。
我们的目标是将nums2合并进nums1，并且保持顺序正确。需要注意的是，nums1数组的大小是m + n，前m个元素是有效的，后面n个元素被初始化为0，我们将使用这些0来填充nums2中的元素。
解题思路如下：
- 因为
nums1的后半部分是空的，我们可以从后往前填充，这样可以避免覆盖nums1中原有的元素。 - 设置两个指针，分别指向
nums1和nums2的最后一个有效元素，还有一个指针指向nums1的最后位置。 - 比较这两个指针所指的元素大小，将较大的数字放入
nums1的最后位置的指针处。 - 移动指针，重复上述过程，直到所有元素都被遍历完。
性能优化关键点：
- 执行速度：从后往前合并可以减少数组元素的移动次数，提高执行速度。
- 内存使用：直接在
nums1数组上操作，无需额外的存储空间，这样可以节省内存。
3. 代码实现
假设nums1 = [1,2,3,0,0,0], m = 3, nums2 = [2,5,6], n = 3。
- 我们设置指针
i为m-1，j为n-1，k为m+n-1。 - 比较
nums1[i]和nums2[j]，nums1[i]=3，nums2[j]=6，将6放入nums1[k]。 - 更新
j和k的值，此时nums1 = [1,2,3,0,0,6]。 - 重复这个过程，直到所有元素都被合并。
下面是C语言的实现代码：
void merge(int* nums1, int nums1Size, int m, int* nums2, int nums2Size, int n) {
int i = m - 1, j = n - 1, 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--];
}
}
这段代码将两个已经排序的整数数组 nums1 和 nums2 合并为一个单一的有序数组。合并的结果存放在 nums1 数组中，合并后的数组也是有序的。
参数说明：
int* nums1：第一个有序数组。int nums1Size：nums1数组的总容量，包括合并后额外的空间。int m：nums1中已有元素的数量，即需要合并的部分。int* nums2：第二个有序数组。int nums2Size：nums2数组的总容量。int n：nums2中的元素数量。
函数逻辑：
-
分别使用三个指针
i，j和k来跟踪nums1，nums2和合并后数组的当前位置。i从nums1的有序部分的末尾开始（索引为m - 1），j从nums2的末尾开始（索引为n - 1），k从合并后数组的末尾开始（索引为m + n - 1）。 -
在
while循环中，比较nums1[i]和nums2[j]的值，并将较大的值放在nums1[k]的位置，然后相应地移动i，j和k指针。 -
如果
nums1[i]大于nums2[j]，则nums1[i]被复制到nums1[k]，然后i和k都递减。 -
如果
nums2[j]大于或等于nums1[i]，则nums2[j]被复制到nums1[k]，然后j和k都递减。 -
这个过程持续直到
i或j中的一个小于 0，意味着其中一个数组已经完全复制到合并后的数组中。 -
如果
nums2有剩余的元素（j >= 0），则需要将这些元素复制到nums1中，因为nums1的剩余部分（如果有）已经是有序的，不需要移动。这一步是必要的，因为在nums1和nums2的合并过程中，如果nums2的元素较小且在前面，需要将它们移动到nums1的前端。
运行结果如下所示:
从运行速率来看，已达到预定目标，所以无需优化(优化需要按照目标来优化，而不能无限制优化下去)。
4. 结论
合并两个有序数组的问题可以通过一种高效的从后向前的填充方法来解决，确保了在不使用额外内存的情况下，合并后的数组nums1仍然保持非递减顺序。这个方法利用了nums1数组预留的空间，通过设置三个指针，逐步比较并填充较大的元素，直到所有元素都被正确合并。这种方法的时间复杂度是O(m+n)，空间复杂度是O(1)，即只需要常数级别的额外空间，因此在执行速度和内存使用方面都非常优化。