Leetcode（88）—— Merge two ordered arrays

subject

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 .

Example 1：

Input ：nums1 = [1,2,3,0,0,0], m = 3, nums2 = [2,5,6], n = 3
Output ：[1,2,2,3,5,6]
explain ： Need merger [1,2,3] and [2,5,6] .
The combined result is [1,2,2,3,5,6] , In which, bold italics indicates nums1 The elements in .

Example 2：

Input ：nums1 = [1], m = 1, nums2 = [], n = 0
Output ：[1]
explain ： Need merger [1] and [] .
The combined result is [1] .

Example 3：

Input ：nums1 = [0], m = 0, nums2 = [1], n = 1
Output ：[1]
explain ： The array to be merged is [] and [1] .
The combined result is [1] .
Be careful , because m = 0 , therefore nums1 No elements in .nums1 The only remaining 0 Just to ensure that the merged results can be successfully stored in nums1 in .

Tips ：

• nums1.length == m + n
• nums2.length == n
• $0$ <= m, n <= $200$
• $1$ <= m + n <= $200$
• $-10^9$ <= nums1[i], nums2[j] <= $10^9$

Advanced ： You can design and implement a time complexity of $O(m+n)$ Does the algorithm solve this problem ？

Answer key

Method 1 ： Sort after direct merge

Ideas

​​   The most intuitive way is to put the array first ${\text{nums}}_2$ Put it in the array ${\text{nums}}_1$ Tail of , Then sort the entire array directly .

Code implementation

class Solution {
    
public:
    void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {
    
        for (int i = 0; i != n; ++i) {
    
            nums1[m + i] = nums2[i];
        }
        sort(nums1.begin(), nums1.end());
    }
};

Complexity analysis

Time complexity ：$O((m+n)log(m+n))$. The length of the sorting sequence is $m+n$, Apply the time complexity of quick sorting , The average is $O((m+n)\log (m+n))$.
Spatial complexity ：$O(\log (m+n))$ The length of the sorting sequence is $m+n$, Because quick sort is used , Therefore, the space complexity of quick sorting can be applied , The average is $O(\log (m+n))$.

Method 2 ： Double pointer + Auxiliary array

Ideas

​​   Method 1 does not utilize arrays ${\text{nums}}_1$ And ${\text{nums}}_2$ The property that has been sorted . In order to take advantage of this property , We can use the double pointer method . This method treats the two arrays as queues , Take out the smaller number from the two array headers at a time and put it into the result . We set a pointer to each of the two arrays $p_1$ And $p_2$ As a pointer to the head of the queue . As shown in the animation below ：

Code implementation

Leetcode Official explanation ：

class Solution {
    
public:
    void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {
    
        int p1 = 0, p2 = 0;
        int sorted[m + n];
        int cur;
        while (p1 < m || p2 < n) {
    
            if (p1 == m) {
    
                cur = nums2[p2++];
            } else if (p2 == n) {
    
                cur = nums1[p1++];
            } else if (nums1[p1] < nums2[p2]) {
    
                cur = nums1[p1++];
            } else {
    
                cur = nums2[p2++];
            }
            sorted[p1 + p2 - 1] = cur;
        }
        for (int i = 0; i != m + n; ++i) {
    
            nums1[i] = sorted[i];
        }
    }
};

Complexity analysis

Time complexity ：$O(m+n)$. The movement of the pointer decreases monotonously , Move at most $m+n$ Time , So the time complexity is zero $O(m+n)$.
Spatial complexity ：$O(m+n)$. Need to establish a length of $m+n$ The middle array of $\text{sorted}$

Method 3 ： Double reverse pointer

Ideas

​​   Method 2 , The reason for using temporary variables , Because if you merge directly into an array ${\text{nums}}_1$ in ,${\text{nums}}_1$ Elements in may be covered before they are removed . So how to avoid coverage directly ${\text{nums}}_1$ And the elements in it ？ Observation can be seen ,${\text{nums}}_1$ The second half of the is empty , Can be covered directly without affecting the results . So you can set the pointer to traverse from back to front , Take the larger of the two at a time and put it in ${\text{nums}}_1$ At the back of .

​​   Strictly speaking , At any point in the traversal ,${\text{nums}}_1$ Array has $m-p_1-1$ Elements are put into ${\text{nums}}_1$ The second half of the ,${\text{nums}}_2$ Array has $n-p_2-1$ Elements are put into ${\text{nums}}_1$ The second half of the , And in the pointer $p_1$ Behind ,${\text{nums}}_1$ Array has $m+n-p_1-1$ A place . because
$$m+n-p_1-1\ge m-p_1-1+n-p_2-1$$

Equivalent to
$$p_2\ge -1$$

Forever , therefore $p_1$ The back position is always enough to hold the inserted element , Will not produce $p_1$ The case where the elements of are covered .

Code implementation

Leetcode Official explanation ：

class Solution {
    
public:
    void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {
    
        int pos = m-- + n-- - 1;
        while (m >= 0 && n >= 0)
            nums1[pos--] = nums1[m] > nums2[n]? nums1[m--]: nums2[n--];
        while (n >= 0)
            nums1[pos--] = nums2[n--];
    }
};

My own ：

class Solution {
    
public:
    void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {
    
        if(n == 0) return;
        while(true){
    
            if(m <= 0){
    
                while(n){
    
                    nums1[n+m-1] = nums2[n-1];
                    n--;
                }
            }
            if(n <= 0) return;
            if(nums1[m-1] >= nums2[n-1]){
    
                nums1[n+m-1] = nums1[m-1];
                m--;
            }else{
    
                nums1[n+m-1] = nums2[n-1];
                n--;
            }
        }
    }
};

Complexity analysis

Time complexity ：$O(m+n)$. The movement of the pointer decreases monotonously , Move at most $m+n$ Time , So the time complexity is zero $O(m+n)$.
Spatial complexity ：$O(1)$. Directly to arrays ${\text{nums}}_1$