信宜市建设局网站营销策划运营培训机构

题目描述：

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

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

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

解法：双数组的双指针遍历

算法思路分析：

整体过程分三步：

• 开一个 m + n 的数组，合并两个有序数组到新开辟的数组内，然后将新开辟的数组拷贝到原数组中。主要的难点就是如何合并两个有序数组。
• 由于两个数组都是非递减的，因此两个数组的首元素一定是它们所处的数组的最小值。那么，我们每一次合并的时候，仅需比较两个数组的首元素，谁最小，谁就是当前所有元素中最小的元素。
• 然后将最小的元素添加到开辟的数组中，并且把最小的元素从原数组中去掉就可以了。

算法流程：

• 开辟一个大小为** m + n** 的数组 ret。
• 初始化三个指针，cur1 = 0, cur2 = 0, dest = 0 分别指向 nums1，nums2，ret 的首元素。
• 当 cur1 < m 并且 cur2 < n 时，一直循环下述过程：
• （思考结束条件：因为我们每次只取出某一个数组中的一个元素，因此，一定有一个数组会先被遍历完，而此时剩下的一个数组的内容，我们只用原封不动的拷贝到 ret 数组中即可。因此，结束条件就是 cur1 或者 cur2 任意一个指针遍历到数组结束位置）
• 比较 nums1[cur1] 与 nums2[cur2] 的大小，分为下面三种：
• nums1[cur1] < nums2[cur2]；说明 nums1[cur1] 是最小的元素，将其放到 ret 数组中，并且让 cur1++（相当于去掉当前元素），dest++（指向下一个元素的位置），因此可以这样写：ret[dest++] = nums1[cur1++]；
• nums1[cur1] = nums2[cur2]；因为此时两个数相等，我们让其中任意一个元素加入到** ret** 数组中均可，因此可以并到上述情况中；
• nums1[cur1] > nums2[cur2]；说明** nums2[cur2]** 是最小的元素，同理可得 ret[dest++] = nums2[cur2++]；
• 处理没有遍历完的数组
• 将没有遍历完的数组全部拷贝到 ret 数组中即可
• 不要忘记将 ret 数组的内容再拷贝到原数组中去

最后整理代码为：

#include <stdio.h>
#include <stdlib.h>void merge(int* nums1, int nums1Size, int m, int* nums2, int nums2Size, int n)
{// 开辟一个新数组，用来存放合并后的结果int* ret = (int*)malloc(sizeof(int) * (m + n));// 初始化三个指针，用来遍历三个数组int cur1 = 0, cur2 = 0, dest = 0;// 当其中一个遍历到数组的结尾，我们就结束循环while (cur1 < m && cur2 < n){// 当第一个数组的元素比较小的时候，我们就加入合并后的数组if (nums1[cur1] <= nums2[cur2])ret[dest++] = nums1[cur1++];// 否则就将第二个元素加入到目标数组elseret[dest++] = nums2[cur2++];}// 下面两个循环只会执行一个，因为只会有一个数组还有剩余元素// 当第一个数组的元素有剩余的话，就会执行第一个循环while (cur1 < m)ret[dest++] = nums1[cur1++]; // 将数组的内容拷贝到合并后的数组中// 当第二个数组的元素有剩余的话，就会执行第二个循环while (cur2 < n)ret[dest++] = nums2[cur2++];// 将合并后的数组，放回第一个数组中去for (int i = 0; i < m + n; i++){nums1[i] = ret[i];}// 释放辅助数组free(ret);
}