Three ways to merge two ordered arrays Java

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
  • -10910^9 <= nums1[i], nums2[i] <=10910^9

Double pointer (extra space)

A simple approach is to create one and nums1nums1 array of equal lengtharrarr , using a double pointer tonum1num1 andnums2nums2 data is migrated toarrarr .

Finally arrarr copied tonums1nums1 .

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)O(m + n)
  • Space complexity:O(m+n)O(m + n)

Merge first and then sort

We can also nums2nums2The content of is first migrated tonums1nums1 go againnums1nums1 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))O((m + n)log{(m + n)})
  • Space complexity:O(1)O(1)

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

Arrays.sort
The "two-axis quick sort" is used, and the space overhead caused by recursion is ignored.


In-situ merger (from front to back)

You can also directly nums1nums1 performs the merge operation, but you need to ensure that each cycle starts,nums2nums2The pointer of must point to the smallest element.

Therefore, we need to nums2nums2 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+m2logm)O(n + m^2 log{m})
  • Space complexity: ignore the recursive overhead, the complexity is O(1)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)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)O(m + n)
  • Space complexity:O(1)O(1)

At last

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

No.88
The series starts on 01/01/2021. As of the starting day, there are 1916 questions on LeetCode, some of which are locked questions. We will first finish all the questions without locks.

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.