算法：合并两个有序数组

提示：文章写完后，目录可以自动生成，如何生成可参考右边的帮助文档

目录

一、问题描述

二、归并排序

总结

提示：以下是本篇文章正文内容，下面案例可供参考

一、问题描述

给定两个有序整数数组?nums1?和?nums2，将?nums2?合并到?nums1?中，使得?num1?成为一个有序数组，nums1中含有m个元素，nums2中含有n个元素，nums1的数组长度大于m+n

二、归并排序

解体思路：

nums1数组中m到m+n-1的位置都是没有元素的，初始状态，两个指针分别指向nums1[m-1]、nums2[n-1]，我们遍历两个数组的尾部，然后将较大的一个放在m+n-1的位置，如果选择的是nums1，则nums1指向nums1前一个元素，即nums1[m-2]；如果选择的是nums2，则nums2指向nums2前一个元素，即nums2[n-2]，一直到两个数组的元素都遍历完。

用一个通俗的例子来举例：

A、B两个班的学生按身高从小到大站两排，现在分别从A班和B班开始报身高，各报一个，如果哪个班的人身高更高，则出列，站到m+n-1的位置。当这个人出列之后，这个班的最高一个人就更新了，然后再开始报身高，出列，一直到所有同学都出列了。

示例代码：

public void merge(int[] arr1, int m, int[] arr2, int n) {
    int i = m - 1;
    int j = n - 1;
    int k = m + n - 1;
    while (i >= 0 && j >= 0) {
        if (arr1[i] > arr2[j]) {
            arr1[k--] = arr1[i--];
        } else {
            arr1[k--] = arr2[j--];
        }
    }
    while (j >= 0) {
        arr1[k--] = arr2[j--];
    }
}

总结

看代码比较枯燥，可以自己在本上画一下，简单到有手就行！?