leetcode 88.合并有序数组（双指针/俩游走下标、数组、java、自实现排序时不要插入）

96 阅读 0 评论 64 点赞

我是靠谱客的博主清脆汽车，这篇文章主要介绍leetcode 88.合并有序数组（双指针/俩游走下标、数组、java、自实现排序时不要插入），现在分享给大家，希望可以做个参考。

方法1：
先推荐看官答的“双指针/从后向前”，把空间复杂度降到了O(1)。
双指针（或者说是俩游走下标）指向两数组最后，自后向前合并。管答中对于简单的if。。else直接用？：来写使代码更凝练。
注意if判断的内容即要求两者都存在元素，那么可能有一方先减到0，所以要再做考虑。

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public void merge(int[] nums1, int m, int[] nums2, int n) {
// two get pointers for nums1 and nums2
int p1 = m - 1;
int p2 = n - 1;
// set pointer for nums1
int p = m + n - 1;
// while there are still elements to compare
while ((p1 >= 0) && (p2 >= 0))
// compare two elements from nums1 and nums2 
// and add the largest one in nums1 
nums1[p--] = (nums1[p1] < nums2[p2]) ? nums2[p2--] : nums1[p1--];
// add missing elements from nums2
System.arraycopy(nums2, 0, nums1, 0, p2 + 1);
}
}

方法2：双指针/自前往后
第一次提交的回答略显繁琐：System.arraycopy(nums2, 0, nums1, 0, p2 + 1)可使用封装的函数；对于简单的if else用？：改写。

合并的实现上，通过空间换取时间，这样不需要在原数组nums1中插入nums2元素而导致大量数据移动造成的时间浪费。
并且通过&&来限制i、j，保证不出现j<n但i>=m时仍有 nums1[i]<=nums2[j] 等情况而导致错误。

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution {
public void merge(int[] nums1, int m, int[] nums2, int n) {
//空间换时间
int nums[]=new int[m+n]; //创建新数组存储所有元素
int i=0;int j=0;int k=0;//数组的游走下标
while(i<m&&j<n){ //注意下标小于临界就是最后一个元素了
if(nums1[i]<=nums2[j]){//j<n但i>=m时有nums1[i]<=情况但不是我们所需要的,while括号内取或后带来的错误情况太多，不如取&& 好好限制下
nums[k++]=nums1[i++];
}else{
nums[k++]=nums2[j++];
}
}
if(i==m&&j!=n){
for(;j<n;j++)
nums[k++]=nums2[j];
}else if(j==n&&i!=m){
for(;i<m;i++)
nums[k++]=nums1[i];
}
//将新建数组赋值给nums1
for(int l=0;l<m+n;l++){ //低级错误int l，后面是i导致复制错误
nums1[l]=nums[l];
}
}
}

时间复杂度O(n+m)
空间复杂度O(n+m) //把nums1的元素先拿出来再直接和并回nums1，O(m)

方法3：管答，使用封装的函数直接复制再排序。。。

复制代码

1
2
3
4
5
6
7
class Solution {
public void merge(int[] nums1, int m, int[] nums2, int n) {
System.arraycopy(nums2, 0, nums1, m, n);
Arrays.sort(nums1);
}
}

时间复杂度 : O((n + m)log(n + m))O((n+m)log(n+m))。
空间复杂度 : O(1)O(1)。

其他解答：双指针/从前往后

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public void merge(int[] nums1, int m, int[] nums2, int n) {
// Make a copy of nums1.
int [] nums1_copy = new int[m];
System.arraycopy(nums1, 0, nums1_copy, 0, m);
// Two get pointers for nums1_copy and nums2.
int p1 = 0;
int p2 = 0;
// Set pointer for nums1
int p = 0;
// Compare elements from nums1_copy and nums2
// and add the smallest one into nums1.
while ((p1 < m) && (p2 < n))
nums1[p++] = (nums1_copy[p1] < nums2[p2]) ? nums1_copy[p1++] : nums2[p2++];
// if there are still elements to add
if (p1 < m)
System.arraycopy(nums1_copy, p1, nums1, p1 + p2, m + n - p1 - p2);
if (p2 < n)
System.arraycopy(nums2, p2, nums1, p1 + p2, m + n - p1 - p2);
}
}

以下代码存在冗余代码，在一开始做这个题的时候通过||来限制i、j ，发现当nums2为空时由于i<m || j<n限制太低导致后面与空元素判断的错误。

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
class Solution {
public void merge(int[] nums1, int m, int[] nums2, int n) {
if(m==0||n==0){ //这一段if内容是冗余的
for(int l=0;l<n;l++)
nums1[l]=nums2[l];
}else {
//空间换时间
int nums[]=new int[m+n]; //创建新数组存储所有元素
int i=0;int j=0;int k=0;//数组的游走下标
while(i<m&&j<n){ //注意下标小于临界就是最后一个元素了
if(nums1[i]<=nums2[j]){//j<n但i>=m时有nums1[i]<=情况但不是我们所需要的,while括号内取或后带来的错误情况太多，不如取&& 好好限制下
nums[k++]=nums1[i++];
}else{
nums[k++]=nums2[j++];
}
}
if(i==m&&j!=n){
for(;j<n;j++)
nums[k++]=nums2[j];
}else if(j==n&&i!=m){
for(;i<m;i++)
nums[k++]=nums1[i];
}
//将新建数组赋值给nums1
for(int l=0;l<m+n;l++){ //低级错误int l，后面是i导致复制错误
nums1[l]=nums[l];
}
}
}
}