合并数组并排序（合并k个排序数组）



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

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

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

题目理解：要求将两个已经按非递减顺序排序的整数数组nums1和nums2进行合并，并且要把合并后的结果直接存储在nums1数组中，也就是原地修改nums1。

已知：nums1初始长度为m+n，其中前m个元素是要参与合并的有效元素，后n个元素初始值为0可忽略；nums2的 长度为n

代码：

代码思路分析：

1.指针初始化；

在merge方法中，首先初始化了三个指针：

 .p1指向nums1中有效元素的末尾，即m-1

 .p2指向nums2中有效元素的末尾，即n-1

 .p指向合并后数组nums1应该存放元素的末尾位置，即 m+n-1

2.比较与合并循环：

通过while循环，只要p1和p2都还没有小于0（也就是两个数组都还有未处理的元素），就进行一下比较和操作：

  .如果nums1[p1] >= nums2[p2]，说明nums1中当前要比较的元素更大或者相等，那么久把nums1[p1]放到合并后的位置p上，然后p1指针往前移一位（p1 -= 1）。

 .反之小于nums1[p1] < nums2[p2],则把nums2[p2]加到合并后的位置p上，同时p2往前移一位

（p2 -= 1）。

 .不管是那种情况，放完元素后，p指针都要往前移一位（p -= 1),p指针都要往前一位（p -= 1）,

以便下一次存放元素到正确的位置。

3.处理剩余元素：

 .当while循环结束后，可能存在nums2还有剩余元素的情况（因为nums1中院士来的元素已经在循环中按顺序处理完的）。

 .此时通过nums1[:p2+1] = nums2[:p2+1] 这行代码，直接将nums2中的剩余袁术（从开头到p2位置）复制到nums1的nums1的开头部分，从而完成整个合并操作

总的来说，这段代码通过双指针的方式，从两个数组的末尾开始比较合并元素，最后在处理可能剩余的元素，实现了将nums2合并到nums1中且保持非递减顺序的要求。

版权声明：

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。
如若内容造成侵权、违法违规、事实不符，请将相关资料发送至xkadmin@xkablog.com进行投诉反馈，一经查实，立即处理！

转载请注明出处，原文链接：https://www.xkablog.com/bcyy/23473.html