菜鸡每日一题系列打卡88天
每天一道算法题目
小伙伴们一起留言打卡
坚持就是胜利，我们一起努力！
题目描述(引自LeetCode)
给你两个有序整数数组nums1和nums2，请你将nums2合并到nums1中，使nums1成为一个有序数组。
说明:
初始化nums1和nums2的元素数量分别为m和n。
你可以假设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]题目分析
这道题目要求合并两个有序数组，之前菜鸡跟大家分享过每日一题——合并两个有序链表，对于顺序结构和链式结构的操作实际上是不同的。
对于数组而言，容易想到的是借助额外的数组空间进行合并，但这样会占用大量额外空间。
这时候，就需要搬出对于数组题目几乎百试百灵的双指针，从而对数组进行原地合并，如何设置双指针是解决问题的重点，菜鸡认为，对本题而言，双指针从后向前遍历数组是比较合适的。
为了使小伙伴对上述两种解答方式有清晰的认识和比较，菜鸡将采用两种方式进行实现。话不多说，上代码！
代码实现
// 借助额外数组空间进行合并 class Solution { public void merge(int[] nums1, int m, int[] nums2, int n) { int[] nums = new int[m + n]; int i = 0, j = 0, k = 0; while (i < m && j < n) nums[k++] = nums1[i] <= nums2[j] ? nums1[i++] : nums2[j++]; while (j < n) nums[k++] = nums2[j++]; for (int l = 0; l < m + n; l++) nums1[l] = nums[l]; } } // 利用双指针进行原地合并 class Solution { public void merge(int[] nums1, int m, int[] nums2, int n) { int i = m - 1, j = n - 1, count = m + n - 1; while (i >= 0 && j >= 0) nums1[count--] = (nums1[i] >= nums2[j]) ? nums1[i--] : nums2[j--]; while (j >= 0) nums1[count--] = nums2[j--]; } }代码分析
对代码进行分析，借助额外数组空间进行合并的方式，时间复杂度为O(m + n)，空间复杂度为O(m + n)。利用双指针进行原地合并的方式，时间复杂度为O(m + n)，空间复杂度为O(1)。
执行结果
借助额外数组空间的运行结果
利用双指针的运行结果
学习 | 工作 | 分享
????长按关注“有理想的菜鸡”
只有你想不到，没有你学不到
