3.ways to merge two ordered arrays Java

This article is participating in the "Java Topics month - Java brush title punch" to view details about active links

Title description

This is 88 on LeetCode. Combine two ordered arrays .

Tag: "Dual pointer", "Sort"

Given two ordered integer arrays nums1 and nums2, please merge nums2 into nums1 to make nums1 an ordered array.

Initialize the number of elements of nums1 and nums2 to m and n respectively.

You can assume that the space size of nums1 is equal to m + n, so that it has enough space to store the elements from nums2.

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]
Copy code

Example 2:

Input: nums1 = [1], m = 1, nums2 = [], n = 0

Output: [1]
Copy code

prompt:

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

Double pointer (extra space)

A simple approach is to create one and $nums1$ array of equal length$arr$ , using a double pointer to$num1$ and$nums2$ data is migrated to$arr$ .

Finally $arr$ copied to$nums1$ .

Code:

class  Solution  {
     public  void  merge ( int [] nums1, int m, int [] nums2, int n)  {
         int total = m + n;
         int [] arr = new  int [total];
         int idx = 0 ;
         for ( int i = 0 , j = 0 ; i <m || j <n;) {
             if (i <m && j <n) {
                arr[idx++] = nums1[i] <nums2[j]? nums1[i++]: nums2[j++];
            } else  if (i <m) {
                arr[idx++] = nums1[i++];
            } else  if (j <n) {
                arr[idx++] = nums2[j++];
            }
        }
        System.arraycopy(arr, 0 , nums1, 0 , total);
    }
}
Copy code

• time complexity:$O(m + n)$
• Space complexity:$O(m + n)$

Merge first and then sort

We can also $nums2$The content of$n$$u$$m$$s$$2$ is first migrated to$nums1$ go again$nums1$ for sorting.

Code:

class  Solution  {
     public  void  merge ( int [] nums1, int m, int [] nums2, int n)  {
        System.arraycopy(nums2, 0 , nums1, m, n);
        Arrays.sort(nums1);
    }
}
Copy code

• time complexity:$O((m + n)log{(m + n)})$
• Space complexity:$O(1)$

PS. The sort sort in Java is a comprehensive sort. Including insertion/dual-axis quick sorting/merge/timsort, it is assumed here

In-situ merger (from front to back)

You can also directly $nums1$ performs the merge operation, but you need to ensure that each cycle starts,$nums2$The pointer of$n$$u$$m$$s$$2$ must point to the smallest element.

Therefore, we need to $nums2$ performs partial sorting.

Code:

class  Solution  {
     public  void  merge ( int [] nums1, int m, int [] nums2, int n)  {
         int i = 0 , j = 0 ;
         while (j <n) {
             if (i >= m) {
                nums1[i] = nums2[j++];
            } else {
                 int a = nums1[i], b = nums2[j];
                 if (a> b) swap(nums1, i, nums2, j);
                sort(nums2, j, n- 1 );
            }
            i++;
        }
    }
    void  sort ( int [] nums, int l, int r)  {
         if (l >= r) return ;
         int x = nums[l], i = l- 1 , j = r + 1 ;
         while (i <j) {
             do i++; while (nums[i] <x);
             do j--; while (nums[j]> x);
             if (i <j) swap(nums, i, nums, j);
        }
        sort(nums, l, j);
        sort(nums, j + 1 , r);
    }
    void  swap ( int [] nums1, int i, int [] nums2, int j)  {
         int tmp = nums1[i];
        nums1[i] = nums2[j];
        nums2[j] = tmp;
    }
}
Copy code

• time complexity:$O(n + m^2 log{m})$
• Space complexity: ignore the recursive overhead, the complexity is $O(1)$

In-situ merger (from back to front)

The idea is similar to "Method 1". It can be done by adjusting the traversal direction from "from front to back" to "from back to front". $O(1)$ Space complexity.

Code:

class  Solution  {
     public  void  merge ( int [] nums1, int m, int [] nums2, int n)  {
         int i = m- 1 , j = n- 1 ;
         int idx = m + n- 1 ;
         while (i> = 0 || j >= 0 ) {
             if (i >= 0 && j >= 0 ) {
                nums1[idx--] = nums1[i] >= nums2[j]? nums1[i--]: nums2[j--];
            } else  if (i >= 0 ) {
                nums1[idx--] = nums1[i--];
            } else {
                nums1[idx--] = nums2[j--];
            }
        }
    }
}
Copy code

• time complexity:$O(m + n)$
• Space complexity:$O(1)$

At last

This is the first in our series of articles on "Brush through LeetCode"

In this series of articles, in addition to explaining the problem-solving ideas, the most concise code will be given as much as possible. If a general solution is involved, the corresponding code template will also be provided.

In order to make it easier for all students to debug and submit code on the computer, I have established a related warehouse: github.com/SharingSour...

In the warehouse address, you can see the link to the solution of the series of articles, the corresponding code of the series of articles, the link to the original question of LeetCode and other preferred solutions.