088.Merge Sorted Array

Posted on | In

Test cases

1
2
3
4
5
6
7
8
9
10
11
12
[1]
1
[]
0
[1,2,3,3,4,7,0,0,0]
6
[6,9,10]
3
[4,5,6,0,0,0]
3
[1,2,3]
3

Solution 1: accepted 0ms

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public void merge(int[] nums1, int m, int[] nums2, int n) {
    m--;
    n--;
    while (m >= 0 || n >= 0) {  // this part is ugly
        if (n < 0) {  // not necessary, the rest of the nums1 is sorted
            nums1[m + n + 1] = nums1[m];
            m--;
        } else if (m < 0) {
            nums1[m + n + 1] = nums2[n];  
            n--;
        } else if (nums1[m] >= nums2[n]) {
            nums1[m + n + 1] = nums1[m];
            m--;
        } else {
            nums1[m + n + 1] = nums2[n];
            n--;
        }
    }
}
Conflict: can’t avoid, we need two loops
1
2
3
4
5
6
7
if (n < 0 || nums1[m] >= nums2[n]) {  // this line will raise error on nums2[n] when n < 0
    nums1[m + n + 1] = nums1[m];
    m--;
} else if (m < 0 || nums2[n] > nums1[m]) {
    nums1[m + n + 1] = nums2[n];
    n--;
}
Improved version
1
2
3
4
5
6
7
8
9
10
11
12
public void merge(int[] nums1, int m, int[] nums2, int n) {
    m--;
    n--;
    while (m >= 0 && n >= 0) {
        nums1[m + n + 1] = nums1[m] >= nums2[n]? nums1[m--] : nums2[n--];
    }
    while (n >= 0) {  // only need to deal with leftovers in nums2
        nums1[m + n + 1] = nums2[n];
        n--;
    }
}