https://leetcode-cn.com/problems/merge-sorted-array/ 给你两个有序整数数组 nums1 和 nums2，请你将 nums2 合并到 nums1 中，使 nums1 成为一个有序数组。
说明: 初始化 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]
法一：除了STL啥都不会的办法 把 nums2 的值复制到 nums1 中，再调用sort。 但本题的意思明显不是问你会不会 sort 函数！！！！！ 时间复杂度O(nlogn) 空间复杂度O(1)
class Solution { public: void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) { for(auto c: nums2) nums1[m++] = c; sort( nums1.begin(), nums1.end() ); } };法二：从前往后排序 这两个从 0 号位置依次比较，如果 nums1[i] > nums[j] ，那么就由 nums[j] 接管 nums1[i] 的位置，否则 nums[j] 跟 nums1[i+1] 比较（谁大谁放在前面）。为了避免原 num1 数组元素被覆盖，我们可以创立个数组 tmp1 用于它来代替比较时的 num1 。 时间复杂度O(n+m)， 遍历n+m次 空间复杂度O(m)，数组 tmp1占m个空间
class Solution { public: void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) { vector<int> tmp1( nums1.begin(), nums1.begin() + m ); //避免nums1数据混乱 int p1 = 0, p2 = 0, pt = 0; while( pt < m && p2 < n ) nums1[p1++] = tmp1[pt] < nums2[p2] ? tmp1[pt++] : nums2[p2++]; while(pt < m) //tmp1还没完 nums1[p1++] = tmp1[pt++]; while(p2 < n) //nums2还没完 nums1[p1++] = nums2[p2++]; } };法三：从后向前 比较 nums1[m–] 和 nums2[n–]，谁大谁在 nums1 末尾。这样从后往前放置在 nums1 中。可充分利用数组的性质。 时间复杂度O(n)，这个 n 当然是 nums2 的 n 啦 空间复杂度O(1)
class Solution { public: void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) { int last = m + n - 1; m --; n --; while(n >= 0) { //nums2处理完了，num1剩余元素是不需要处理的,毕竟有序数组嘛 if( m >= 0 && nums1[m] > nums2[n] ) nums1[last--] = nums1[m--]; else nums1[last--] = nums2[n--]; } } };不懂就问 为啥同样的写法，人家占内存却比我的小？？？只击败不到10%不甘心。
这是我修改过后的写法：
class Solution { public: void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) { int last = m + n - 1; m--; n--; while( m >= 0 && n >= 0 ) nums1[last--] = nums1[m] > nums2[n] ? nums1[m--] : nums2[n--]; while( n >= 0) nums1[last--] = nums2[n--]; } };这是内存占用最少的写法：
