88 [Leetcode] Merge Sorted Array 合并数组

Merge Sorted Array

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

Note: You may assume that nums1 has enough space (size that is greater or equal to m + n) to hold additional elements from nums2. The number of elements initialized in nums1 and nums2 are m and n respectively.

倒序存储

复杂度

时间 O(N+M) 空间 O(1)

思路

提示第一个数组的大小足以装两个数组，所以自然想到把两个数组都合并到第一个数组中，但是第一个数组前面都是有用的信息，如果直接从前面加，我们得将后面所有的数都位移。但是如果我们从后往前，合并到第一个数组的最后，则不用位移。

注意

将m和n都先减1，用m和n来代表下标，避免两个数组为空时抛出空指针异常。

代码

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

/**
 * 本代码由九章算法编辑提供。没有版权欢迎转发。
 * - 九章算法致力于帮助更多中国人找到好的工作，教师团队均来自硅谷和国内的一线大公司在职工程师。
 * - 现有的面试培训课程包括：九章算法班，系统设计班，九章强化班，Java入门与基础算法班，
 * - 更多详情请见官方网站：http://www./
 */

class Solution {
    /**
     * @param A: sorted integer array A which has m elements, 
     *           but size of A is m+n
     * @param B: sorted integer array B which has n elements
     * @return: void
     */
    public void mergeSortedArray(int[] A, int m, int[] B, int n) {
        int i = m-1, j = n-1, index = m + n - 1;
        while (i >= 0 && j >= 0) {
            if (A[i] > B[j]) {
                A[index--] = A[i--];
            } else {
                A[index--] = B[j--];
            }
        }
        while (i >= 0) {
            A[index--] = A[i--];
        }
        while (j >= 0) {
            A[index--] = B[j--];
        }
    }
}