Monday, May 1, 2017

88. Merge Sorted Array

Given two sorted integer arrays nums1 and nums2, merge nums2 into nums1 as one sorted array.
Note:
You may assume that nums1 has enough space (size that is greater or equal to m + n) to hold additional elements from nums2. The number of elements initialized in nums1 and nums2 are m and n respectively.



Solution:

If we put numbers from left to right, it is likely that after one operation, we have to move all the rest numbers in array nums1 one position to the right. The time complexity is O(n) for this operation.

So we insert the numbers from right to left to avoid such complexity.

In each insertion, we insert the largest number of the two arrays to the right of nums1. And update the pointers.

When either pointer reaches 0, we know all the numbers in one array has been inserted. We need to insert the rest of the other array.

If there are left overs in nums2, we put them into nums1.

If there are left overs in nums1, since they are already in order, we do not need to do anything.

The time complexity is O(n) since we check each element only once.



Code:


public class Solution {
    public void merge(int[] nums1, int m, int[] nums2, int n) {
        int index = m + n - 1;
        int p1 = m - 1;
        int p2 = n - 1;
        while (p1 >= 0 && p2 >= 0) {
            if (nums1[p1] > nums2[p2]) {
                nums1[index--] = nums1[p1--];
            }
            else {
                nums1[index--] = nums2[p2--];
            }
        }
        while (p2 >= 0) {
            nums1[index--] = nums2[p2--];
        }
    }
}