:-: 1.8 合并两个有序数组 ***** **题干：** 给定两个有序整数数组 nums1 和 nums2，将 nums2 合并到 nums1 中，使得 num1 成为一个有序数组。 说明: 1. 初始化 nums1 和 nums2 的元素数量分别为 m 和 n。 2. 你可以假设 nums1 有足够的空间（空间大小大于或等于 m + n）来保存 nums2 中的元素。 示例: ``` 输入: nums1 = [1,2,3,0,0,0], m = 3 nums2 = [2,5,6], n = 3 输出: [1,2,2,3,5,6] ``` **题目分析：** 此题是将nums2数组中的元素合并到nums1数组中，输出的是nums1数组，我们可以通过倒序添加、临时数组，直接添加再排序的三种方式来达到目的。 **新手有可能遇到的解题思路陷阱：** 正序原数组操作，此操作困难且难以实现，使用临时数组时条件判断不充分。 **解题思路分析以及代码实现：** 第一种思路：临时数组法，条件判断要充分，防止出现数组越界情况。 第一种思路代码： ``` public void merge(int[] nums1, int m, int[] nums2, int n) { if (n == 0) { return; } int temp[] = new int[m + n]; int i = 0, j = 0, k = 0; while (k < m + n) { if (i >= m || j < n && nums1[i] > nums2[j]) { temp[k] = nums2[j]; j++; } else if (j >= n || i < m && nums1[i] <= nums2[j]) { temp[k] = nums1[i]; i++; } k++; } for (int e = 0; e < m + n; e++) { nums1[e] = temp[e]; } } ``` **复杂度分析** 时间复杂度：O(n)。 空间复杂度：O(n)。 第二种思路：直接添加后排序法。 第二种思路代码： ``` public void merge(int[] nums1, int m, int[] nums2, int n) { if (n == 0) { return; } for (int i = m; i < m + n; i++) { nums1[i] = nums2[i - m]; } Arrays.sort(nums1); } ``` **复杂度分析** 时间复杂度：O(n)。 空间复杂度：O(1)。 第三种思路：倒叙添加。 第三种思路代码： ``` public void merge(int[] nums1, int m, int[] nums2, int n) { int i = m - 1, j = n - 1, len = m + n - 1; // 从num1的最后开始往前插入数据 while (i >= 0 && j >= 0) { if (nums1[i] < nums2[j]) { nums1[len--] = nums2[j--]; } else { nums1[len--] = nums1[i--]; } } // 如果nums1中没有元素直接将nums2中的元素放入nums1 if (i < 0) { while (j >= 0) { nums1[len--] = nums2[j--]; } } } ``` **复杂度分析** 时间复杂度：O(n)。 空间复杂度：O(1)。 **若有理解错误的、写错的地方、更好的思路，方法，望各位读者评论或者发邮件指正或指点我，不胜感激。**