88. Merge Sorted Array

Given two sorted integer arrays nums1 and nums2, merge nums2 into nums1 as one sorted array.

Note: You may assume that nums1 has enough space (size that is greater or equal to m + n) to hold additional elements from nums2. The number of elements initialized in nums1 and nums2 are m and n respectively.

题解

合并已排序的数组nums2到nums1，已知num1有足够的空间

下意识写了个归并排序的整合，使用额外空间O(m)，时间复杂度O(m+n)。

class Solution { public: void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) { int i = 0, j = 0, k = 0; vector<int> haha = nums1; while(i < m && j < n){ if(haha[i] < nums2[j]) nums1[k++] = haha[i++]; else nums1[k++] = nums2[j++]; } while(i < m) nums1[k++] = haha[i++]; while(j < n) nums1[k++] = nums2[j++]; } };

后来发现完全不需要开辟额外空间，只需要反向（从大到小）放置，就可以避免正向时的覆盖问题。

class Solution { public: void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) { while(n) nums1[m + n - 1] = (m == 0 || nums1[m - 1] < nums2[n - 1]) ? nums2[--n] : nums1[--m]; } };