88.合并两个有序数组（双指针）

172 阅读 0 评论 114 点赞

我是靠谱客的博主欢喜心情，这篇文章主要介绍88.合并两个有序数组（双指针），现在分享给大家，希望可以做个参考。

88.合并两个有序数组（双指针）　　　　　　　　难度：简单

题目描述：
给你两个有序整数数组 nums1 和 nums2，请你将 nums2 合并到 nums1 中，使 nums1 成为一个有序数组。

初始化 nums1 和 nums2 的元素数量分别为 m 和 n 。你可以假设 nums1 的空间大小等于 m + n，这样它就有足够的空间保存来自 nums2 的元素。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/merge-sorted-array
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

考察的是双指针：采用贪心的策略，保证每次操作都是局部最优的，从而使最后得到的结果是全局最优的。

我的思路：
1.设置三个指针：p1、p2分别对应nums1、nums2的m-1和n-1位；
　　　　　　　　p对应nums1的m+n-1位。
2.进行判断，具体见程序
3.易错点：注意当m=0,n>0的情况

我的Java代码：

复制代码

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

int[] nums1 = new int[] {0};
int m = 0;
int[] nums2 = new int[] {1};
int n = 1;
int p = m + n - 1;
int p1 = m - 1;
int p2 = n - 1;
//方法二：
while(p1>=0 && p2>=0){
nums1[p--] = (nums1[p1]>nums2[p2])?nums1[p1--]:nums2[p2--];
}
while(p2>=0){
nums1[p--] = nums2[p2--];
}
System.out.println(Arrays.toString(nums1));
//方法一：先直接合并，再sort();这方法孬的一比，不讲武德！
//
for(int i=m;i<nums1.length;i++){
//
nums1[i] = nums2[i-m];
//
}
//
Arrays.sort(nums1);
//
System.out.println(Arrays.toString(nums1));