Merge Sorted Array

Given two sorted integer array s nums 1 and nums 2, merge nums 2 into nums 1 as 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 nums1and nums2 are m and n respectively.

图例

分析

1. use the logic of two pointers : slow pointer : k , fast pointer: either i or j ,whichever is bigger
2. since there will be enough space for nums2, we will use a virtual space in nums1 from index m+n-1 to index 0
3. becasue nums1 and nums2 are sorted, plus nums2 's length is shorter. we use two pointer : i, j to scan nums1 , nums2 seperately. if nums1[i] > nums2[j] we assign nums[i] to nums1[k], otherwise, we assign nums[j] to nums1[k]
4. after assignment, k should decrement closer to index of 0

代码

class Solution {
    public void merge(int[] nums1, int m, int[] nums2, int n) {
        int k = m+n-1;
        int i = m-1;
        int j = n-1;

        while(j>=0){
            if(i>=0 && nums1[i]>nums2[j]){
                nums1[k] = nums1[i];
                i--;
            }else {
                nums1[k] = nums2[j];
                j--;
            }
            k--;
        }

    }
}