房地产网站建设的目的,wordpress删除顶部,外贸网站 服务器,南昌公众号开发公司题目描述#xff1a; 给你两个按 非递减顺序 排列的整数数组 nums1 和 nums2#xff0c;另有两个整数 m 和 n #xff0c;分别表示 nums1 和 nums2 中的元素数目。 请你 合并 nums2 到 nums1 中#xff0c;使合并后的数组同样按 非递减顺序 排列。 注意#xff1a;最终 给你两个按 非递减顺序 排列的整数数组 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 分别指向 nums1nums2ret 的首元素。当 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.hvoid 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);
}
