文章目录

• Merge Sorted Array 合并两个有序数组
• • 问题描述：
  • 分析
  • 代码
  • • Sort
  • Tag

Merge Sorted Array 合并两个有序数组

问题描述：

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

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

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

n u m s 1. l e n g t h = = m + n n u m s 2. l e n g t h = = n 0 < = m , n < = 200 1 < = m + n < = 200 − 1 09< = n u m s 1 [ i ] , n u m s 2 [ j ] < = 1 09 nums1.length == m + n\\ nums2.length == n\\ 0 <= m, n <= 200\\ 1 <= m + n <= 200\\ -10^9 <= nums1[i], nums2[j] <= 10^9nums1.length==m+nnums2.length==n0<=m,n<=2001<=m+n<=200−109<=nums1[i],nums2[j]<=109

分析

常见的处理方式，就不赘述了。

先说结论，从尾部进行双指针。

$nums1$长度为$m+n$,$num2$长度为$n$，但是$nums1$中只有前m个是有效的数据。
所以定义3个指针，

• p1 表示nums1中最后一个数字
• p2 表示nums2中最后一个数字。
• p = m+n-1,表示nums1中可以放入数字的位置。

整个过程可以看成是一个逆向的归并。
注意指针的移动，别越界，当一个指针小于0时，就可以单独处理另一个指针。

代码

Sort

public void merge(int[] nums1, int m, int[] nums2, int n) {int p1 = m-1,p2 = n-1,idx = m+n-1;while( idx>=0 ){if(p1>=0&&p2>=0){if(nums2[p2]>=nums1[p1]){nums1[idx--] = nums2[p2--];}else{nums1[idx--] = nums1[p1--];}}else if(p1>=0){nums1[idx--] = nums1[p1--];}else{nums1[idx--] = nums2[p2--];}}return;}

时间复杂度$O(M+N)$

空间复杂度$O(1)$

Tag

Array

Sort

Two Pointers