/**
 * 88. Merge Sorted Array
 * 1. Time:O(m+n)  Space:O(m)
 * 2. Time:O(m+n)  Space:O(1)
 */

// 1. Time:O(m+n)  Space:O(m)
class Solution {
    public void merge(int[] nums1, int m, int[] nums2, int n) {
        int[] tmp = Arrays.copyOfRange(nums1,0,m);
        int i=0,j=0;
        for(int k=0;k<nums1.length;k++){
            if(i>=m)
                nums1[k] = nums2[j++];
            else if(j>=n)
                nums1[k] = tmp[i++];
            else if(tmp[i]<nums2[j])
                nums1[k] = tmp[i++];
            else
                nums1[k] = nums2[j++];
        }
    }
}

// 2. Time:O(m+n)  Space:O(1)
class Solution {
    public void merge(int[] nums1, int m, int[] nums2, int n) {
        int i=m-1,j=n-1,k=m+n-1;
        while(i>=0 && j>=0){
            nums1[k--] = nums1[i]>=nums2[j]? nums1[i--]:nums2[j--];
        }
        while(j>=0)
            nums1[k--] = nums2[j--];
    }
}