合并两个有序数组-力扣88（数组+逆向+双指针+c）

分手后的思念是犯贱 2023-01-13 09:22 133阅读 0赞

题目描述：  
给你两个有序整数数组 nums1 和 nums2，请你将 nums2 合并到 nums1 中，使 nums1 成为一个有序数组。

初始化 nums1 和 nums2 的元素数量分别为 m 和 n 。你可以假设 nums1 的空间大小等于 m + n，这样它就有足够的空间保存来自 nums2 的元素。

示例 1：

输入：nums1 = \[1,2,3,0,0,0\], m = 3, nums2 = \[2,5,6\], n = 3  
输出：\[1,2,2,3,5,6\]  
示例 2：

输入：nums1 = \[1\], m = 1, nums2 = \[\], n = 0  
输出：\[1\]

提示：

nums1.length == m + n  
nums2.length == n  
0 <= m, n <= 200  
1 <= m + n <= 200  
\-109 <= nums1\[i\], nums2\[i\] <= 109

来源：力扣（LeetCode）  
链接：https://leetcode-cn.com/problems/merge-sorted-array  
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

题解：  
分析：这道题目思路比较容易想到，见缝插针就可以了。

*  由于两个数组是排好序的，初始化两个指针 i , j i,j i,j分别指向数组1与数组2的头
 *  然后通过比较数组2中的  j j j元素是否比数组1中的 i i i元素小，如果小的话，就让数组1的 i i i之后的元素（包括i）后移一位，将数组二中的 j j j元素插到 i i i处， i i i指针与 j j j指针右移，数组1的长度m加1；否则 i i i后移.
 *  最后，数组2中剩余的元素说明比数组1的最后一个元素还要大，由于数组2是排好序的，所以直接把数组2剩余的元素放到当前数组1的后面就可以了。
 *  时间复杂度是 O ( m 2 + n ) O(m^2 + n) O(m2\+n)，空间复杂度是O(1)，由于涉及到数组1的移位操作，所以时间复杂度较高，可以通过设置新的数组来使时间复杂度为 O ( m + n ) O(m + n) O(m\+n)，此时空间复杂度为 O ( m + n ) O(m + n) O(m\+n)。

代码如下：

void merge(int* nums1, int nums1Size, int m, int* nums2, int nums2Size, int n){ 
        int i = 0;
        int j = 0;
    
        while( i < m && j < n)
        { 
            if(nums2[j] <= nums1[i])
            { 
                for(int k = m - 1; k >= i; k--)
                { 
                    nums1[k+1] = nums1[k];
                }
                nums1[i] = nums2[j];
                i++;
                j++;
                m++;
            }
            else
            { 
                 i++;
            }
        }
        while(j < n)
        { 
             nums1[i] = nums2[j];
             i++;
             j++;
        }
    
    }

改进：  
其实上面的方法由于是从前往后去往数组1中放元素，所以会涉及到数组的移位操作，其实我们可以从后往前向数组1中放元素，这样就不会涉及到数组的移位操作了，时间复杂度就可以降低到$O(m+n)了。  
具体操作：

*  同样设置两个指针，初始化两个指针 p 1 , p 2 p1,p2 p1,p2分别指向数组1与数组2的尾
 *  比较 p 1 , p 2 p1,p2 p1,p2指向元素的大小，把大的元素放到数组1的最后面(m+n-1处)，通过双指针控制这个过程，直到某个指针为-1，此时把剩余的指针指向的数组的其余元素放到数组1中就可以了
 *  为什么这样不会覆盖数组1中的元素：  
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM4MDQ4NzU2_size_16_color_FFFFFF_t_70]

void merge(int* nums1, int nums1Size, int m, int* nums2, int nums2Size, int n){ 
        int p1 = m-1;
        int p2 = n-1;
        int tail = m + n - 1;
        int curr;
    
        while( p1>=0 || p2 >=0)
        { 
    
             if(p1 == -1)
             { 
                  curr = nums2[p2--];
             }
             else if(p2 == -1)
             { 
                  curr = nums1[p1--];
             }
             else if(nums1[p1] > nums2[p2])
             { 
                  curr = nums1[p1--];
             }
             else
             { 
                  curr = nums2[p2--];
             }
             nums1[tail--] = curr;
        }
    
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM4MDQ4NzU2_size_16_color_FFFFFF_t_70]: /images/20221022/211f8e672bf544b7bb9a1e3f8cbcdeec.png