考试结束，班级平均分只拿到了年级第二，班主任于是问道:大家都知道世界第一高峰珠穆朗玛峰，有人知道世界第二高峰是什么吗？正当班主任要继续发话，只听到角落默默想起来一个声音:”乔戈里峰”
前言
2018.11.16号打卡
明天的题目leetcode66：
https://leetcode-cn.com/problems/plus-one/
题目
每天一道leetcode88-合并两个有序数组
分类：链表
中文链接：
https://leetcode-cn.com/problems/merge-sorted-array/
英文链接
https://leetcode.com/problems/merge-sorted-array/
题目详述
给定两个有序整数数组 nums1 和 nums2，将 nums2 合并到 nums1 中，使得 num1 成为一个有序数组。
说明:
初始化 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]
题目详解
使用额外空间的思路
- 混合插入有序数组，由于两个数组都是有序的，所有只要按顺序比较大小即可。最先想到的方法是建立一个m+n大小的新数组，然后逐个从A和B数组中取出元素比较，把较小的加入新数组，然后在考虑A数组有剩余和B数组有剩余的两种情况，最后在把新数组的元素重新赋值到A数组中即可。
代码
1class Solution {
2 public void merge(int[] nums1, int m, int[] nums2, int n) {
3 int [] result = new int[m+n];
4 int i =0,j=0,k=0;
5 while(i < m && j < n)
6 {
7 if(nums1[i] < nums2[j]){
8 result[k++] = nums1[i++];
9 }else{
10 result[k++] = nums2[j++];
11 }
12 }
13 if(i != m)
14 {
15 while(i < m)
16 {
17 result[k++] = nums1[i++];
18 }
19 }
20 if(j != n)
21 {
22 while(j < n)
23 {
24 result[k++] = nums2[j++];
25 }
26 }
27 k = 0;
28 for(i=0;i<nums1.length;i++)
29 nums1[i] = result[k++];
30
31 }
32}
代码讲解
- 5-12行，比较num1数组与nums2数组，哪个小，就存入result中
- 13-26行 就是两个数组，可能有一个没遍历完，那么把这个没遍历完的继续添加到result数组后面
- 28-29行 就是把result数组复制到nums1中。
不使用额外空间的思路
- 由于合并后A数组的大小必定是m+n，所以从最后面开始往前赋值，先比较A和B中最后一个元素的大小，把较大的那个插入到m+n-1的位置上，再依次向前推。如果A中所有的元素都比B小，那么前m个还是A原来的内容，没有改变。如果A中的数组比B大的，当A循环完了，B中还有元素没加入A，直接用个循环把B中所有的元素覆盖到A剩下的位置。
代码
1class Solution {
2 public void merge(int[] nums1, int m, int[] nums2, int n) {
3 int k = m + n - 1;
4 int i = m-1;int j = n-1;
5 while(i >=0 && j >= 0)
6 {
7 if(nums1[i] > nums2[j])
8 {
9 nums1[k--] = nums1[i--];
10 }else{
11 nums1[k--] = nums2[j--];
12 }
13 }
14 if(i > 0)
15 {
16 while(i >= 0)
17 {
18 nums1[k--] = nums1[i--];
19 }
20 }
21 if(j >= 0)
22 {
23 while(j >= 0)
24 {
25 nums1[k--] = nums2[j--];
26 }
27 }
28 }
29}
代码讲解
- 5-13行就是从数组nums1和数组nums2的后面开始遍历，谁大就把谁存到nums1的后面（这里注意看示例，nums1的后面是一堆0，代表空闲的空间，m和nums1的数组长度是不一样的~）
- 14-20行 就是如果nums1前面有数字没遍历完，那么就把nums1的数字继续保留到nums1中，其实这6行代码可以不要，因为nums1的数字就是有序的，不需要再次复制了，nums1的前面的数字已经存在于nums1中了；
- 21-27行 就是如果nums2前面还有数字没遍历完，那么就把nums2中数字复制到nums1中，这里是必须要要用到，因为nums2中数字可不在nums1中。
结束语
2018.11.16号打卡
作者乔戈里亲历2019秋招，哈工大计算机本硕，百度准入职java工程师，欢迎大家关注我的微信公众号：程序员乔戈里，公众号有3T编程资源，以及我和我朋友（准入职百度C++工程师）在秋招期间整理的近200M的面试必考的java与C++面经，并有每天一道leetcode打卡群与技术交流群，欢迎关注。
