Merge two ordered arrays of order table OJ

One Title Description

Here are two buttons Non decreasing order Array of arranged integers  nums1 and nums2, There are two other integers m and n , respectively nums1 and nums2 The number of elements in .

Would you please Merge nums2 To nums1 in , Make the merged array press Non decreasing order array .

Be careful ： Final , The merged array should not be returned by the function , It's stored in an array nums1 in . In response to this situation ,nums1 The initial length of is m + n, The top m Elements represent the elements that should be merged , after n Elements are 0 , It should be ignored .nums2 The length of is n .

source ： Power button （LeetCode）
link ：https://leetcode.cn/problems/merge-sorted-array
Copyright belongs to the network . For commercial reprint, please contact the official authority , Non-commercial reprint please indicate the source .

Two Ideas

Merge two ordered arrays , Then you need to define three pointers . A pointer points to the end of the first array , The second pointer points to the end of the second array , These two pointers are used to adjust the order of the sorted array , Another pointer points to the last position of the array , Used to identify the location where data is stored .

Because it stores data from the back to the front , So compare the value pointed to by the first and second pointers , Take the larger one and put it at the position marked by the third pointer . Then continue to look for the next one , Then the third pointer should point forward . The pointer in the array that has taken out a data also needs to point forward .

Until the data in one of the two arrays is stored .

At this point we need to consider ： If the data in the second array is stored first , Then there is no need to continue the operation , Because the data is ultimately stored in the first array , The second array is stored first , Explain that the remaining arrays are ordered .

If the first array is stored first , Then we need to store the elements in the second array in the first array in turn , Because after the previous comparison and sorting , The smallest element in the first array will also be larger than the largest element in the second array at this time , So directly storing the elements in the second array into the first array can ensure the order of the elements in the array .

The illustration ：

Code implementation ：

void merge(int* nums1, int nums1Size, int m, int* nums2, int nums2Size, int n){

int n1=m-1;
int n2=n-1;
int pos=m+n-1;

while(n1>=0&&n2>=0)
{
    if(nums1[n1]>nums2[n2])
    {
        nums1[pos]=nums1[n1];
        n1--;
        pos--;
    }
    else
    {
        nums1[pos]=nums2[n2];
        n2--;
        pos--;
    }
}
while(n2>=0)
{
    nums1[pos]=nums2[n2];
        n2--;
        pos--;
}

}