LeetCode - Merge Sorted Array
Problem 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:
1
2
3
4
5
Input:
nums1 = [1,2,3,0,0,0], m = 3
nums2 = [2,5,6], n = 3
Output: [1,2,2,3,5,6]
Analysis
Just use insert index to get a O(n) space complexity solution.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class Solution {
public void merge(int[] nums1, int m, int[] nums2, int n) {
int i = 0;
int j = 0;
int insertIndex = 0;
int[] vals = new int[m];
for (int l = 0; l < m; l++){
vals[l]=nums1[l];
}
while(i< m || j < n){
int v1 = i == m? Integer.MAX_VALUE: vals[i];
int v2 = j == n? Integer.MAX_VALUE:nums2[j];
if (v1 < v2){
nums1[insertIndex++] = vals[i];
i++;
}
else{
nums1[insertIndex++] = nums2[j];
j++;
}
}
}
}
However, if we start from the end, we can get a O(1) SC solution.
1
2
3
4
5
6
7
8
9
10
class Solution {
public void merge(int[] nums1, int m, int[] nums2, int n) {
while(n>0){
if(m<=0 || nums1[m-1]< nums2[n-1])
nums1[m+n-1]=nums2[--n];
else
nums1[m+n-1]=nums1[--m];
}
}
}
What to improve
- if we have to save information from the beginning, we can start from the end to save space.