代码训练LeetCode(1)合并有序数组详解

代码训练(1)LeetCode之合并两个有序数组

Author: Once Day Date: 2024年3月5日

漫漫长路，才刚刚开始…

全系列文章可参考专栏: 十年代码训练_Once-Day的博客-CSDN博客

参考文章:

88. 合并两个有序数组 - 力扣（LeetCode）
力扣 (LeetCode) 全球极客挚爱的技术成长平台

文章目录

- - 代码训练(1)LeetCode之合并两个有序数组
  - - 1. 问题
    - 2. 分析
    - 3. 代码实现
    - 4. 结论

1. 问题

给你两个按非递减顺序排列的整数数组 nums1 和 nums2，另有两个整数 m 和 n ，分别表示 nums1 和 nums2 中的元素数目。

请你合并 nums2 到 nums1 中，使合并后的数组同样按非递减顺序排列。

注意：最终，合并后数组不应由函数返回，而是存储在数组 nums1 中。为了应对这种情况，nums1 的初始长度为 m + n，其中前 m 个元素表示应合并的元素，后 n 个元素为 0 ，应忽略。nums2 的长度为 n 。

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)，即只需要常数级别的额外空间，因此在执行速度和内存使用方面都非常优化。

Alt