题意:有两个排好升序的数组A1,A2,内存在A1的末尾有足够多的空余位置容纳A2,请实现一个函数,把A2中所有的数字插入到A1中,并且所有的数字都是排序的。
nums1.length == m + n
nums2.length == n
题解:本题和【剑指offer|2.替换空格】类似,由于在合并数组(字符串)时,如果从前往后移动每一个数字都需要重复移动数字多次,因此我们可以考虑从后往前移动,从而提高效率。
void merge(int* nums1, int nums1Size, int m, int* nums2, int nums2Size, int n){
//目标就是把nums2中的元素挪完-->end2==>0
//下面的deadLine,end1,end2都是对应的下标--双指针
int deadLine=m+n-1;
int end1=m-1;
int end2=n-1;
while(end1>=0&&end2>=0)
{
if(nums1[end1]>nums2[end2])
{
nums1[deadLine--]=nums1[end1--];
}
else
{
nums1[deadLine--]=nums2[end2--];
}
}
//到这里如果end2==0的话,就说明num2挪完了,任务完成了;如果是end1==0的话,直接把nums2中剩余元素挪动到num1中即可
if(end1<0)
{
while(end2>=0)
{
nums1[deadLine--]=nums2[end2--];
}
}
}
吐槽一下:这个参数num1Size属实有点多余!
class Solution {
public:
void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {
int deadLine=nums1.size()-1;
int end1=m-1;
int end2=n-1;
while(end1>=0&&end2>=0)
{
if(nums1[end1]>nums2[end2])
{
nums1[deadLine--]=nums1[end1--];
}
else
{
nums1[deadLine--]=nums2[end2--];
}
}
if(end1<0)
{
while(end2>=0)
{
nums1[deadLine--]=nums2[end2--];
}
}
}
};