LeetCode088_88. 合并两个有序数组

一、描述

给你两个按非递减顺序排列的整数数组 nums1 和 nums2，另有两个整数 m 和 n ，分别表示 nums1 和 nums2 中的元素数目。

请你合并 nums2 到 nums1 中，使合并后的数组同样按非递减顺序排列。

注意：最终，合并后数组不应由函数返回，而是存储在数组 nums1 中。为了应对这种情况，nums1 的初始长度为 m + n，其中前 m 个元素表示应合并的元素，后 n 个元素为 0 ，应忽略。nums2 的长度为 n 。

示例 1：

输入：nums1 = [1,2,3,0,0,0], m = 3, nums2 = [2,5,6], n = 3
输出：[1,2,2,3,5,6]
解释：需要合并 [1,2,3] 和 [2,5,6] 。
合并结果是 [1,2,2,3,5,6] ，其中斜体加粗标注的为 nums1 中的元素。

示例 2：

输入：nums1 = [1], m = 1, nums2 = [], n = 0
输出：[1]
解释：需要合并 [1] 和 [] 。
合并结果是 [1] 。

示例 3：

输入：nums1 = [0], m = 0, nums2 = [1], n = 1
输出：[1]
解释：需要合并的数组是 [] 和 [1] 。
合并结果是 [1] 。
注意，因为 m = 0 ，所以 nums1 中没有元素。nums1 中仅存的 0 仅仅是为了确保合并结果可以顺利存放到 nums1 中。

提示：

nums1.length == m + n
nums2.length == n
0 <= m, n <= 200
1 <= m + n <= 200
-10 9 <= nums1[i], nums2[j] <= 10 9

二、题解

方法一：新创建一个数组，将数组nums1中前m个元素和数组nums2排序完放在新数组中，然后排序，最后将新数组值重新给数组nums1。

    /*** 题意：将nums1中的前m个元素和nums2中的前n个元素合并到nums1中，并排序前m+n个元素。* 思路：新创建一个数组，将数组nums1中前m个元素和数组nums2排序完放在新数组中，然后排序，最后将新数组值重新给数组nums1。*///AC Your runtime beats 48.00 % of java submissions.//59 / 59 test cases passed.	Status: Accepted	Runtime: 6 mspublic void merge(int[] nums1, int m, int[] nums2, int n) {int[] nums3 = new int[m + n];//定义一个临时的数组for (int i = 0; i < m; i++) {nums3[i] = nums1[i];}for (int i = 0; i < n; i++) {nums3[m + i] = nums2[i];}Arrays.sort(nums3);for (int i = 0; i < nums3.length; i++) {nums1[i] = nums3[i];//重新赋值给nums1}//System.out.println(Arrays.toString(nums1));}

方法二：和上面的思路类似，但是更简洁

    //和上面的思路类似，但是更简洁public void merge2(int[] nums1, int m, int[] nums2, int n) {for (int i = 0; i < n; i++) {nums1[m + i] = nums2[i];}Arrays.sort(nums1);//System.out.println(Arrays.toString(nums1));}

方法三：双指针。这应该是本题的意义所在

    //方法三：双指针。这应该是本题的意义所在public void merge(int[] nums1, int m, int[] nums2, int n) {//定义双指针int index1 = 0;int index2 = 0;int[] sortArr = new int[m + n];int curValue;//表示在当前的排序数组中要存放的值while (index1 < m || index2 < n) {if (index1 == m) {curValue = nums2[index2++];} else if (index2 == n) {curValue = nums1[index1++];} else if (nums1[index1] < nums2[index2]) {curValue = nums1[index1++];} else {curValue = nums2[index2++];}sortArr[index1 + index2 - 1] = curValue;}for (int i = 0; i < m + n; i++) {nums1[i] = sortArr[i];}//System.out.println(Arrays.toString(nums1));}

LeetCode 1. 两数之和
LeetCode 2. 两数相加
LeetCode 3. 无重复字符的最长子串
LeetCode 4. 寻找两个正序数组的中位数
LeetCode 5. 最长回文子串
LeetCode 6. Z 字形变换
LeetCode 7. 整数反转
LeetCode 8. 字符串转换整数 (atoi)
LeetCode 9. 回文数
LeetCode 10. 正则表达式匹配
LeetCode 13. 罗马数字转整数
LeetCode 14. 最长公共前缀
LeetCode 20. 有效的括号本
LeetCode 26. 删除有序数组中的重复项
LeetCode 27. 移除元素
LeetCode 28. 找出字符串中第一个匹配项的下标
LeetCode 35. 搜索插入位置
LeetCode 53. 最大子数组和
LeetCode 66. 加一
LeetCode 67. 二进制求和
LeetCode 69. x 的平方根
LeetCode 70. 爬楼梯
LeetCode 80. 删除有序数组中的重复项 II
LeetCode 83. 删除排序链表中的重复元素
LeetCode 82. 删除排序链表中的重复元素 II
LeetCode 88. 合并两个有序数组