今天学习了LeetCode的合并两个有序数组 作为第一个学习的算法有一点纪念意义故记录。
关于合并双指针数组，题目为：
给你两个按 非递减顺序 排列的整数数组 nums1和 nums2，另有两个整数 m 和 n ，分别表示 nums1 和 nums2 中的元素数目。
请你 合并 nums2到 nums1 中，使合并后的数组同样按 非递减顺序 排列。
注意：最终，合并后数组不应由函数返回，而是存储在数组 nums1 中。为了应对这种情况，nums1 的初始长度为 m + n，其中前 m 个元素表示应合并的元素，后 n 个元素为 0 ，应忽略。nums2 的长度为 n 。
共有三种解法，第一种解法感觉有点像逃课，有点赖皮
class Solution { public: void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) { for(int i = 0;i!=n;i++) { nusm1[m+i]=nums2[i]; } sort[nums1.begin(),nums1.end()]; } };
第二种解法属于双指针，利用nums1和nums2已经遍历的前提，个人理解为新建一个新的数据域，再创建两个指针指向已有的nums1和nums2，将两个数组视为队列，通过指针遍历将小的那个数放入创建的新的数据域，最后再赋给nums1。
class Solution { public: void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) { int p1 = 0 ,p2 = 0; int sorted[m+n]; int cur; while(p1<m || p2<n) { if(p1 == m) { cur = nums2[p2++]; } else if(p2 == n) { cur = nums1[p1++]; } else if(nums1[p1]<nums2[p2]) { cur = nums1[p1++]; } else { cur = nums2[p2++]; } sorted[p1+p2-1]=cur; } for(int i = 0;i!=m+n;++i) { nums1[i]=sorted[i]; } } };
第三种解法为逆向双指针，上一种解法开创了一个新的空间所以空间复杂度为O（m+n），而逆向双指针的空间复杂度为O（1），因为不用开创新的空间直接原地在nums1进行修改。而关于这一部分说实话不能够完全理解
方法二中，之所以要使用临时变量，是因为如果直接合并到数组 nums1 中，nums1中的元素可能会在取出之前被覆盖。那么如何直接避免覆盖 nums1 中的元素呢？观察可知，nums1的后半部分是空的，可以直接覆盖而不会影响结果。因此可以指针设置为从后向前遍历，每次取两者之中的较大者放进 nums1的最后面。
严格来说，在此遍历过程中的任意一个时刻，nums1 数组中有 m−p1−1 个元素被放入 nums1 的后半部，nums2 数组中有 n−p2−1个元素被放入 nums1 的后半部，而在指针 p1 的后面，nums1 数组有 m+n−p1−1 个位置。由于
m+n−p1−1≥m−p1−1+n−p2−1
等价于
p2≥−1
永远成立，因此 p1后面的位置永远足够容纳被插入的元素，不会产生 p1的元素被覆盖的情况。
class Solution { public: void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) { int p0=m-1,p1=n-1; int tail = m+n-1; int cur; while(p0>=0 || p1>=0) { if(p0==-1) { cur = nums2[p1--]; } else if(p1==-1) { cur = nums1[p0--]; } else if(nums1[p0] > nums2[p1]) { cur = nums1[p0--]; } else { cur = nums2[p1--]; } nums1[tail--]=cur; } } };
学习之路任重而道远，加油！