双指针 [e] #88. Merge Sorted Array

2021-01-21 https://leetcode.com/problems/merge-sorted-array/

Description

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

The number of elements initialized in nums1 and nums2 are m and n respectively. You may assume that nums1 has a size equal to m + n such that it has enough space to hold additional elements from nums2.

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

思路总结：

1. 本题重点是指针起始值要设在数组结尾，从尾向头遍历。否则在 nums1 上归并得到的值会覆盖还未进行归并比较的值。
2. 除了nums1, nums2 两个指针 还要设置一个merge后nums1的指针，起始值为：n+m-1。
3. 先考虑边界值：数组1为空，或数组2为空两种特殊情况，再考虑插入位置。
4. syntax特殊用法：

sum[i++] = 2; \\ 等同于sum[i] = 2; i++;

Solution：

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