88. Merge Sorted Array.md

88. Merge Sorted Array

Question:

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]

Thinking:

• Method:
  • 需要从后向前比较。
  • 参考了Merge Sorted Array

class Solution {
    public void merge(int[] nums1, int m, int[] nums2, int n) {
        int writeIndex = nums1.length;
        int index1 = m, index2 = n;
        while(index1 > 0 || index2  > 0){
            int cur1 = (index1 > 0) ? nums1[--index1] : Integer.MIN_VALUE;
            int cur2 = (index2 > 0) ? nums2[--index2] : Integer.MIN_VALUE;
            if(cur2 >= cur1){
                if(cur1 != Integer.MIN_VALUE)
                    index1++;
                nums1[--writeIndex] = cur2;
            }
            else{
                if(cur2 != Integer.MIN_VALUE)
                    index2++;
                nums1[--writeIndex] = cur1;
            }
        }
    }
}

二刷

二刷想到了从后往前，并且对于index的操作更优雅了。

class Solution {
    public void merge(int[] nums1, int m, int[] nums2, int n) {
        int index = nums1.length - 1, index1 = m - 1, index2 = n - 1;
        while(index >= 0 && (index1 >= 0 || index2 >= 0)){
            if(index1 >= 0 && index2 >= 0){
                if(nums1[index1] > nums2[index2]){
                    nums1[index--] = nums1[index1--];
                }else
                    nums1[index--] = nums2[index2--];
            }else if(index1 >= 0 && index2 < 0)
                nums1[index--] = nums1[index1--];
            else
                nums1[index--] = nums2[index2--];
        }
    }
}