【leetcode-面试经典 150 题】-1.合并两个有序数组

题目：

给你两个按 非递减顺序 排列的整数数组 nums1 和 nums2，另有两个整数 m 和 n ，分别表示 nums1 和 nums2 中的元素数目。

请你 合并 nums2 到 nums1 中，使合并后的数组同样按 非递减顺序 排列。

注意：最终，合并后数组不应由函数返回，而是存储在数组 nums1 中。为了应对这种情况，nums1 的初始长度为 m + n，其中前 m 个元素表示应合并的元素，后 n 个元素为 0 ，应忽略。nums2 的长度为 n 。

分析：首先看到这是两个非递减顺序排列的整数数组，就想到利用双指针来解决该问题。顺便回顾一下双指针的板子。

首先是同向指针，把数组分成三个部分：[0,i)，在这个区间的数据代表处理过并且我需要的数据，[i,j)这个区间代表我处理过但是不需要的数据，[ j , arr.length)代表我们目前没有处理过的数据。

1.定义两个指针i和j，并且i和j一般都等于0。
2.while j < arr.length:
	if 如果说我们需要arr[j]，那么我们就让arr[i] = arr[j],然后i往前走
	一步，让它指向下一个位置。
	else 如果不需要j这个元素，那么我们就跳过arr[j]这个元素，让j指向下一
	个位置，同时不需要改变i的位置。

其次是异向指针，[0,i)和(j,arr.length)都是已经处理好的数据，是我们需要的，[i,j]是我们待处理的元素。

1.定义双指针,i = 0,j = arr.length - 1.
2.while i <= j:
	根据arr[i] 和 arr[j]的值来确定你接下来要做什么。
	移动至少一个指针向他们自身的方向

参考：看这一篇就够啦，双指针题型解题模板总结_双指针模板-CSDN博客

具体到本次的题目，若是利用同向指针。就是每次按照规则（那个小）取出数组1或者数组2的元素，放进另一个数组中，最终将该数组的值赋值给数组1,即满足题目要求。其中i为数组1的指针，j为数组2的指针。分为四种情况。

其他三种情况类似，就不一一解释，下面放代码：

class Solution {
    public void merge(int[] nums1, int m, int[] nums2, int n) {
        int i=0,j=0;
        int temp = 0;
        int[] nums3 = new int[m+n+1];
        while (i<m || j<n){
            if (i == m){
                temp = nums2[j++];
            }else if (j == n){
                temp = nums1[i++];
            }else if (nums1[i] < nums2[j]){
                temp = nums1[i++];
            }else {
                temp = nums2[j++];
            }
            nums3[i+j-1]=temp;
        }
        for (int k = 0; k!=m+n;k++){
            nums1[k] = nums3[k];
        }
    }
}