88. Merge Sorted Array (Easy) Facebook Microsoft Bloomberg

Given two sorted integer arraysnums1andnums2, mergenums2intonums1as one sorted array.

Note:
You may assume that nums1 has enough space (size that is greater or equal tom+n) to hold additional elements from nums2. The number of elements initialized in nums1 and nums2 are m and n respectively.

Solution 1: 同向Two Pointers O(n + m); O(1)

    /**
     * 同向Two Pointers O(n + m);O(1)
     * One pointer i at the end of nums1. Another pointer j at the end of nums2.
     * Compare their values and put the larger one at the end of nums1.
     * The index is m+n-1. If m == 0, nums1 is fully merged, merge the rest of nums2.
     */
    public void merge(int[] nums1, int m, int[] nums2, int n) {
        while (n > 0) {
            nums1[m + n - 1] = (m == 0 || nums1[m - 1] < nums2[n - 1]) ? nums2[--n] : nums1[--m];
        }
    }
}

Solution 2: 同向Two Pointers O(n + m); O(1) 推荐写这个，好解释

    public void merge(int[] nums1, int m, int[] nums2, int n) {
        int i = m - 1;
        int j = n - 1;
        int k = m + n - 1;
        while (i >= 0 && j >= 0) {
            if (nums1[i] < nums2[j]) {
                nums1[k--] = nums2[j--];
            } else {
                nums1[k--] = nums1[i--];
            }
        }
        while (j >= 0) {
            nums1[k--] = nums2[j--];
        }
    }