88. Merge Sorted Array (1)

Link

Given two sorted integer arrays nums1 and nums2, merge nums2 into nums1 as one sorted array.

Note:

• The number of elements initialized in nums1 and nums2 are m and n respectively.

• You may assume that nums1 has enough space (size that is greater or equal to m + n) to hold additional elements from nums2.

Example:

Input:
nums1 = [1,2,3,0,0,0], m = 3
nums2 = [2,5,6],       n = 3

Output: [1,2,2,3,5,6]

Solution

class Solution {
    public void merge(int[] nums1, int m, int[] nums2, int n) {
        int nums1Index = m-1;
        int nums2Index = n-1;
        //從後面開始merge會較容易
        for(int i = n + m -1; i >= 0; i--){
            if( nums1Index >= 0 && nums2Index >= 0){
                //兩個array從尾端開始比較，把比較大的依序放到array後端
                if(nums1[nums1Index] > nums2[nums2Index]){
                    nums1[i] = nums1[nums1Index];
                    nums1Index--;
                }
                else{
                    nums1[i] = nums2[nums2Index];
                    nums2Index--;
                }
            }
            //若nums1先放完，表示剩下的都是nums2的，就一一填入即可
            else if (nums1Index < 0){
                nums1[i] = nums2[nums2Index];
                nums2Index--;
            }
            //若nums2先放完，表示剩下的都是nums1的，就一一填入即可
            //可不做，因為nums1的元素本身就已經在nums1裡了
            else if (nums2Index < 0){
                nums1[i] = nums1[nums1Index];
                nums1Index--;
            }
        }
    }
}