title: Merge Sorted Array
tags:
- merge-sorted-array
- No.88
- simple
- array
- modulus
- in-place
Description
Given two sorted integer arrays nums1 and nums2, merge nums2 into nums1 as one sorted array.
Note:
- The number of elements initialized in nums1 and nums2 are m and n respectively.
- You may assume that nums1 has enough space (size that is greater or equal to m + n) to hold additional elements from nums2.
Example:
Input:
nums1 = [1,2,3,0,0,0], m = 3
nums2 = [2,5,6], n = 3
Output: [1,2,2,3,5,6]
Corner Cases
- empty
nums2 - two empty arrays
-
nums1larger thannums2 -
nums1smaller thannums2 - too lange array that overflows when being copied
- same values
- positive and negative infinity
2147483647&-2147483648 - single value arrays
-
very important case
nums1={0}, m=0
Solutions
Merge Sort Copying Array
This algorithm is the same with merge part in merge sort. We can do it with copying array.
For java, it's difficult to extend array, thus difficult to construct a new slot to save infinity 2147483647. We can use modulus to accomplish this target, as long as we set the visited slot to be infinity.
Running time is O(m+n).
class Solution {
public void merge(int[] nums1, int m, int[] nums2, int n) {
if (nums1.length == 0 || nums2.length == 0) {return;}
if (m == 0) {
for (int k=0; k<n; k++) {
nums1[k] = nums2[k];
}
return;
}
int[] tnums = Arrays.copyOfRange(nums1, 0, m);
boolean flag;
int i = 0;
int j = 0;
int k = 0;
for (; k<m+n; k++) {
flag = (tnums[i] < nums2[j]);
nums1[k] = flag ? tnums[i] : nums2[j];
tnums[i] = flag ? 2147483647 : tnums[i];
nums2[j] = flag ? nums2[j] : 2147483647;
i = flag ? (i + 1)%m : i%m;
j = flag ? j%n : (j + 1)%n;
}
}
}
Merge Sort In Place
The straightforward approach by copying nums1 to an auxiliary array is easy to implement. However, when the size of the array is large, it is problematic to do so. Thus an in-place algorithm is prefered. Though easy it might seem, the fact is that it is quite complicated to implement. Besides, it's difficult to maintain the linear time complexity O(n).
