面试经典 150 题 ---- 合并两个有序数组

合并两个有序数组

方法一：直接合并后排序

这种方法最简单，直接将 nums2 的数组放到 nums1 数组的尾部，然后对 nums1 进行排序即可

class Solution {public void merge(int[] nums1, int m, int[] nums2, int n) {for (int i = 0; i < n; i ++ ) {nums1[i + m] = nums2[i];}Arrays.sort(nums1);}
}

时间复杂度： O((m + n)log(m + n))
数组长度为 m + n，快排的时间复杂度为 O((m + n)log(m + n))

空间复杂度： O((m + n)log(m + n))
数组长度为 m + n，快排的时间复杂度为 O((m + n)log(m + n))

方法二：双指针

方法一没有使用到数组已经被排序的性质。利用这一性质，我们可以使用双指针方法。将两个数组看作队列，每次从数组的头部取出一个比较小的值放到结果中。

class Solution {public void merge(int[] nums1, int m, int[] nums2, int n) {int p1 = 0, p2 = 0;int[] sorted = new int[m + n];int cur = 0;while (p1 < m || p2 < n) {if (p1 == m) {sorted[cur] = nums2[p2++];} else if (p2 == n) {sorted[cur] = nums1[p1++];} else if (nums1[p1] < nums2[p2]) {sorted[cur] = nums1[p1++];} else {sorted[cur] = nums2[p2++];}cur ++ ;}for (int i = 0; i < m + n; i ++ ) {nums1[i] = sorted[i];}}
}

时间复杂度： O(m + n)
指针单调移动，最多移动 m + n 次，因此时间复杂度为 O(m + n)

空间复杂度： O(m + n)
需要建立长度为 m + n 的中间数组

方法三：逆向双指针

方法二需要使用临时变量，是因为直接合并到 nums1 中，nums1 中的元素可能会在取出之前被覆盖。那么如何直接避免覆盖 nums1 中的元素呢？可以使用双指针从后往前遍历，每次取两者之中的比较大者放进 nums1 的最后面。

为什么从后往前，将大的元素放入到 nums1 中就不会出现覆盖元素的情况呢？
可以这样想象。如果是将 nums2 中的元素放入了 nums1 中，那么此时 nums1 的元素肯定不会被覆盖，如果是将 nums1 中的元素放入了 nums1 的后半部分，nums1 的前半部分就肯定会出现一个空位，从而保证全部元素都可以放进去且不会发生覆盖。

class Solution {public void merge(int[] nums1, int m, int[] nums2, int n) {int p1 = m - 1, p2 = n - 1;int cur = nums1.length - 1;while(p1 >= 0 || p2 >= 0) {if (p1 == -1) {nums1[cur -- ] = nums2[p2 -- ];} else if (p2 == -1) {nums1[cur -- ] = nums1[p1 -- ];} else if (nums1[p1] > nums2[p2]) {nums1[cur -- ] = nums1[p1 -- ];} else {nums1[cur -- ] = nums2[p2 -- ];}}}
}

时间复杂度： O(m + n)
指针单调移动，最多移动 m + n 次，因此时间复杂度为 O(m + n)

空间复杂度： O(m + n)
直接对 nums1 原地修改，不需要额外的空间