LeetCode题目官网地址：力扣
Java实现代码：
?package array;
??
?import java.util.Arrays;
??
?/**
? * @ClassName LeetCode 88.合并两个有序数组
? * @Description https://leetcode.cn/problems/merge-sorted-array/
? * @Author Jiangnan Cui
? * @Date 2022/10/31 20:36
? * @Version 1.0
? */
?public class LeetCode88 {
? ? /**
? ? ? * @MethodName merge
? ? ? * @Description 方法1：先将数组nums2放进数组nums1的尾部，然后直接对整个数组进行排序。
? ? ? * ? ? ? ? ? ? 注意：Java内置的排序算法为快速排序
? ? ? * ? ? ? ? ? ? 时间复杂度：O((m+n)*log(m+n))，其中，m+n表示合并后数组的长度
? ? ? * ? ? ? ? ? ? 空间复杂度：O(log(m+n))
? ? ? * ? ? ? ? ? ? 满足题目要求，但不推荐使用，因为没有利用到题目中提到的数组递增有序的性质
? ? ? * @param: nums1
? ? ? * @param: m
? ? ? * @param: nums2
? ? ? * @param: n
? ? ? * @Author Jiangnan Cui
? ? ? * @Date 20:38 2022/10/31
? ? ? */
? ? public void merge(int[] nums1, int m, int[] nums2, int n) {
? ? ? ? // 合并方式1：利用for循环逐个赋值
?// ? ? ? for (int i = 0; i < n; i++) {
?// ? ? ? ? ? nums1[i + m] = nums2[i];
?// ? ? ? }
? ? ? ? // 合并方式2：利用Java内置数组的复制方法实现
? ? ? ? // ? ? ? ? ? ? ? 原数组，起始位置，目标数组，起始位置，复制长度
? ? ? ? System.arraycopy(nums2, 0, nums1, m, n);
? ? ? ? // 利用Java内置的排序算法进行排序
? ? ? ? Arrays.sort(nums1);
? ? }
??
? ? /**
? ? ? * @MethodName merge2
? ? ? * @Description 方法2：双指针法，利用数组nums1与nums2已经被排序的性质，指向两个数组元素的指针从左到右依次比较，将较小的元素放到结果数组中
? ? ? * ? ? ? ? ? ? 时间复杂度：O(m+n)，其中，m+n表示合并后数组的长度
? ? ? * ? ? ? ? ? ? 空间复杂度：O(m+n)
? ? ? * ? ? ? ? ? ? 满足题目要求
? ? ? * @param: nums1
? ? ? * @param: m
? ? ? * @param: nums2
? ? ? * @param: n
? ? ? * @Author Jiangnan Cui
? ? ? * @Date 20:38 2022/10/31
? ? ? */
? ? public void merge2(int[] nums1, int m, int[] nums2, int n) {
? ? ? ? // 数组nums1的指针p1，最开始指向最左侧
? ? ? ? int p1 = 0;
? ? ? ? // 数组nums2的指针p2，最开始指向最左侧
? ? ? ? int p2 = 0;
? ? ? ? // 为避免直接放在nums1数组中的元素被覆盖，需要一个额外的结果数组
? ? ? ? int[] result = new int[m + n];
? ? ? ? // 记录保存到result的值
? ? ? ? int cur;
? ? ? ? // 遍历两个数组，保证两个数组下标均不越界
? ? ? ? while (p1 < m || p2 < n) { // 需要两个数组均访问到头才能结束
? ? ? ? ? ? // 如果数组1遍历到头，数组2还未遍历到头，直接存入数组2剩下的元素
? ? ? ? ? ? if (p1 == m) {
? ? ? ? ? ? ? ? cur = nums2[p2++];
? ? ? ? ? ? }
? ? ? ? ? ? // 如果数组2遍历到头，数组1还未遍历到头，直接存入数组1剩下的元素
? ? ? ? ? ? else if(p2 == n) {
? ? ? ? ? ? ? ? cur = nums1[p1++];
? ? ? ? ? ? }
? ? ? ? ? ? // 如果数组1对应的元素小，就把该元素放入结果数组中，同时p1++，向右遍历
? ? ? ? ? ? else if(nums1[p1] <= nums2[p2]) {
? ? ? ? ? ? ? ? cur = nums1[p1++];
? ? ? ? ? ? }
? ? ? ? ? ? // 如果数组2对应的元素小，就把该元素放入结果数组中，同时p2++，向右遍历
? ? ? ? ? ? else{
? ? ? ? ? ? ? ? cur = nums2[p2++];
? ? ? ? ? ? }
? ? ? ? ? ? // 每次存入一个元素，数组下标为p1+p2-1，即两个指针当前指向前已经比较出的元素个数，对应下标需要减1
? ? ? ? ? ? result[p1 + p2 - 1] = cur;
? ? ? ? }
? ? ? ? // 最终要将结果放入nums1数组中
? ? ? ? for (int i = 0; i < m + n; i++) {
? ? ? ? ? ? nums1[i] = result[i];
? ? ? ? }
? ? }
??
? ? /**
? ? ? * @MethodName merge3
? ? ? * @Description 方法3：逆向双指针法，对方法2进行优化
? ? ? * ? ? ? ? ? ? 指针从右向左遍历，每次取两者之中的较大者放进nums1数组的最后面，不会发生元素被覆盖的情况
? ? ? * ? ? ? ? ? ? 时间复杂度：O(m+n)，其中，m+n表示合并后数组的长度
? ? ? * ? ? ? ? ? ? 空间复杂度：O(1)
? ? ? * ? ? ? ? ? ? 满足题目要求
? ? ? * @param: nums1
? ? ? * @param: m
? ? ? * @param: nums2
? ? ? * @param: n
? ? ? * @Author Jiangnan Cui
? ? ? * @Date 20:38 2022/10/31
? ? ? */
? ? public void merge3(int[] nums1, int m, int[] nums2, int n) {
? ? ? ? // 数组nums1的指针p1，最开始指向最右侧
? ? ? ? int p1 = m - 1;
? ? ? ? // 数组nums2的指针p2，最开始指向最右侧
? ? ? ? int p2 = n - 1;
? ? ? ? // 从右向左记录有效结果的索引下标
? ? ? ? int tail = nums1.length - 1;
? ? ? ? // 只要p2到达开头就行了，数组1的元素始终在数组1里面且有序
? ? ? ? while (p2 >= 0) { // nums2数组到达头部结束
? ? ? ? ? ? // 数组1到头，数组2还未到头，将数组2的元素存进nums1
? ? ? ? ? ? if(p1 < 0) {
? ? ? ? ? ? ? ? nums1[tail--] = nums2[p2--];
? ? ? ? ? ? }
? ? ? ? ? ? // 数组1的元素小于数组2的元素，将数组2的元素存到nums1最右侧
? ? ? ? ? ? else if (nums1[p1] <= nums2[p2]) {
? ? ? ? ? ? ? ? nums1[tail--] = nums2[p2--];
? ? ? ? ? ? }
? ? ? ? ? ? // 数组2的元素小于数组1的元素，将数组1的元素存到nums1最右侧
? ? ? ? ? ? else{
? ? ? ? ? ? ? ? nums1[tail--] = nums1[p1--];
? ? ? ? ? ? }
? ? ? ? }
? ? }
??
? ? public static void main(String[] args) {
? ? ? ? int[] nums1 = new int[]{1, 2, 3, 0, 0, 0};
? ? ? ? int m = 3;
? ? ? ? int[] nums2 = new int[]{2, 5, 6};
? ? ? ? int n = 3;
? ? ? ? new LeetCode88().merge(nums1, m, nums2, n);
? ? ? ? System.out.println("nums1 = " + Arrays.toString(nums1));
??
? ? ? ? int[] nums12 = new int[]{1, 2, 3, 0, 0, 0};
? ? ? ? int m2 = 3;
? ? ? ? int[] nums22 = new int[]{2, 5, 6};
? ? ? ? int n2 = 3;
? ? ? ? new LeetCode88().merge2(nums12, m2, nums22, n2);
? ? ? ? System.out.println("nums12 = " + Arrays.toString(nums12));
??
? ? ? ? int[] nums123 = new int[]{1, 2, 3, 0, 0, 0};
? ? ? ? int m23 = 3;
? ? ? ? int[] nums223 = new int[]{2, 5, 6};
? ? ? ? int n23 = 3;
? ? ? ? new LeetCode88().merge3(nums123, m23, nums223, n23);
? ? ? ? System.out.println("nums123 = " + Arrays.toString(nums123));
? ? }
?}
输出结果：
?nums1 = [1, 2, 2, 3, 5, 6] ?nums12 = [1, 2, 2, 3, 5, 6] ?nums123 = [1, 2, 2, 3, 5, 6]
详细可参考：?力扣
