2021.4.5

88. 合并两个有序数组

https://leetcode-cn.com/problems/merge-sorted-array/
给你两个有序整数数组 nums1 和 nums2，请你将 nums2 合并到 nums1 中，使 nums1 成为一个有序数组。

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

 

示例 1：

输入：nums1 = [1,2,3,0,0,0], m = 3, nums2 = [2,5,6], n = 3
输出：[1,2,2,3,5,6]

示例 2：

输入：nums1 = [1], m = 1, nums2 = [], n = 0
输出：[1]

提示：

 nums1.length == m + n
 nums2.length == n
&emsp;0 <= m, n <= 200
&emsp;1 <= m + n <= 200
&emsp;-10^9 <= nums1[i], nums2[i] <= 10^9

学到的知识点：双指针
&emsp;看到题：合并起来然后排序（
&emsp;但是这样做的话时间复杂度是O(m*lg m)，而且完全没有利用到两个数组的有序性
&emsp;那么可以借用一下归并排序的思路，从大到小维护两个指针（实际上是两个Index），然后将两数组中的数字从大到小写入nums1中即可。
&emsp;最终代码1（合并后排序）：（C#）

public class Solution {
    public void Merge(int[] nums1, int m, int[] nums2, int n) {
        for(int i=m;i<m+n;i++){
            nums1[i]=nums2[i-m];
        }
        Array.Sort(nums1);
    }
}

&emsp;真短。
&emsp;最终代码2（双指针）：（C#）

public class Solution {
    public void Merge(int[] nums1, int m, int[] nums2, int n) {
        int i=m-1;//用i指示nums1中的数字
        int j=n-1;//用j指示nums2中的数字
        int index=m+n-1;//用index指示nums1中已经写入数字的位置
        while(i>=0 && j>=0){
            //将nums1和nums2中最大的数比较，然后将较大的写入nums1的index处
            if(nums1[i]>=nums2[j]){
                nums1[index--] = nums1[i--];
            }
            else{
                nums1[index--] = nums2[j--];
            }
        }
        //如果数字还有剩下的，那么他们一定比已经写入的数字都小，则直接将其写入nums1前面没有进行写入的位置
        while(i>=0){
            nums1[index--] = nums1[i--];
        }
        while(j>=0){
            nums1[index--] = nums2[j--];
        }
    }
}