LeetCode中合并两个有序数组题解-java
题目
88. 合并两个有序数组
难度简单723
给你两个有序整数数组 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]
提示:
-10^9 <= nums1[i], nums2[i] <= 10^9
nums1.length == m + n
nums2.length == n
题解
方法一:合并后排序
思路
将两个数组进行合并,然后对其进行排序
代码实现
class Solution {
public void merge(int[] nums1, int m, int[] nums2, int n) {
for(int i = 0; i < n; i++){
nums1[m++] = nums2[i];
}
Arrays.sort(nums1);
}
}
复杂度分析
- 时间复杂度 : O*((n+m)log(n+m))。
- 空间复杂度 :O*(1)。
提交详情
方法二:双指针从前往后排序
思路
使用P1和P2两个指针,分别为两个数组的头部,在每一步中比较两个指针所在元素的大小,将较小值放在输出数组中,然后,对应指针后移一步,直到两个指针有一方到达尾部,将另一方其余全部元素放在输出数组中
代码实现
class Solution {
public void merge(int[] nums1, int m, int[] nums2, int n) {
// 新建一个数组,复制nums1,作为nums1的副本
int[] nums1Copy = new int[m];
for(int i = 0; i < m; i++){
nums1Copy[i] = nums1[i];
}
// 双指针,分别指向nums1Copy和nums2的头部
int p1 = 0;
int p2 = 0;
// 指向输出数组nums1的头部
int p = 0;
// 当p1 和 p2 双指针均在两个数组之内时
while((p1 < m) && (p2 < n)){
// 输出数组p指针所在的值即为:p1,p2 两个指针所在值的较小值,并将较小值所在指针++,然后p指针向后移一位
nums1[p++] = (nums1Copy[p1] < nums2[p2]) ? nums1Copy[p1++] : nums2[p2++];
}
// 如果p1指针未到尾部,将剩余部分全部复制到输出数组中
if(p1 < m){
for(int j = p1; j < m; j++){
nums1[p++] = nums1Copy[j];
}
}
// 若P2指针未到尾部,将剩余部分复制到输出数组中
if(p2 < n){
for(int i = p2; i < n; i++){
nums1[p++] = nums2[i];
}
}
}
}
复杂度分析
- 时间复杂度 : O*(n+*m)。
- 空间复杂度 : O*(m)。
提交详情
方法三:双指针,从后往前
思路
使用P1和P2两个指针,分别为两个数组的尾部,在每一步中比较两个指针所在元素的大小,将较大值放在输出数组中,然后,对应指针前移一步,直到两个指针有一方到达头部,将另一方其余全部元素放在输出数组中
代码实现
class Solution {
public void merge(int[] nums1, int m, int[] nums2, int n) {
// 新建两个指针p1,p2, 分别指向两个数组的尾部
int p1 = m -1;
int p2 = n -1;
// 新建一个指针p,指向nums1 的尾部
int p = m + n - 1;
// 当p1,p2指针均未到达头部时,
while((p1 >= 0) && (p2 >= 0)){
// 此时数组元素为两个指针指向的元素的较大值,之后,对应指针--,总指针p--
nums1[p--] = (nums1[p1] < nums2[p2]) ? nums2[p2--] : nums1[p1--];
}
// 如果p1 < 0 ,此时数组2还未到达头部,此时将p2 指针到头部中的元素全部复制给数组
for(int i = p2; i >= 0; i--){
nums1[p--] = nums2[i];
}
// 如果p2 < 0 ,说明数组p1未到达头部,但此时nums1以有原来元素,故不需要复制
}
}
复杂度分析
- 时间复杂度 : O(n + m)O(n+m)。
- 空间复杂度 : O(1)O(1)。