Small knowledge, big challenge! This article is participating in the creation activity of “Essential Tips for Programmers”.

Merges two ordered arrays

You are given two non-descending arrays of integers, nums1 and nums2, and two integers, m and n, representing the number of elements in nums1 and nums2, respectively. Please merge nums2 into nums1 so that the merged array is also in non-descending order.

Note: Finally, the merged array should not be returned by the function, but stored in the array nums1. To deal with this, nums1 has an initial length of m + n, where the first m elements represent the elements that should be combined and the last n elements are 0 and should be ignored. Nums2 has a length of n.

  • Example 1:

    Input: nums1 =,2,3,0,0,0 [1], m = 3, nums2 = [6] 2, n = 3 output:,2,2,3,5,6 [1] : need to merge [1, 2, 3] and [6] 2. The combined result is [1,2,2,3,5,6], where the elements in italics and bold are nums1.Copy the code

  • Example 2:

    Input: nums1 = [1], m = 1, nums2 = [], n = 0 Output: [1] Description: Combine [1] and []. The combined result is [1].Copy the code

Example 3:

Input: nums1 = [0], m = 0, nums2 = [1], n = 1 Output: [1] Description: The arrays to be merged are [] and [1]. The combined result is [1]. Note that there are no elements in nums1 because m = 0. The only zeros left in NUMs1 are simply to ensure that the merge results can be safely stored in NUMs1.Copy the code

Tip:

nums1.length == m + n
nums2.length == n
0 <= m, n <= 200
1 <= m + n <= 200
-109 <= nums1[i], nums2[j] <= 109
Copy the code

[Advanced] : Can you design and implement a time complexity O(m + N) algorithm to solve this problem?

Source: LeetCode

2. The Method of violence

// java
class Solution {
    public void merge(int[] nums1, int m, int[] nums2, int n) {
        // If nums2 is empty, return nums2
        if(n==0) {return ;
        }
        // If nums1 is empty, assign the value of nums2 to nums1 and return
        if (m==0) {for(int i = 0; i<n; i++){ nums1[i] = nums2[i]; }return ;
        }
        
        // nums1 and nums2 are not empty
        for(inti = m; i<m+n; i++){ nums1[i] = nums2[i-m]; }// Sort the merged nums1Arrays.sort(nums1); }}Copy the code

[Three-pointer method]

// Three Pointers:
// two Pointers p1 and p2 refer to the last non-zero element of nums1 and nums2, traversing backwards
// The third pointer tail points to the end of nums1
// Place the large numbers at the end of nums1, in order to the front
The length of nums1 is exactly equal to the total length of the two arrays
// Because no element is moved, the time complexity is O(m+n),
// No extra space is used, so the space complexity is O(1)
public static void merge(int[] nums1, int m, int[] nums2, int n) {
    int p1 = m - 1;
    int p2 = n - 1;
    int tail = m + n - 1;
    while (p2 >= 0) {
        nums1[tail--] = (p1 >= 0&& nums1[p1] > nums2[p2]) ? nums1[p1--] : nums2[p2--]; }}Copy the code