leetcode刷题（32）——88. 合并两个有序数组
leetcode刷题（32）——88. 合并两个有序数组
给定两个有序整数数组 nums1 和 nums2，将 nums2 合并到 nums1 中，使得 num1 成为一个有序数组。
说明: 初始化 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]方法1： 投机取巧，感觉面试并不会喜欢这种解法，直接两个合并为一个数组，然后用Api进行排序，但此方法没有利用到两个数组都是分别已经排序好的特点。
class Solution {
public void merge(int[] nums1, int m, int[] nums2, int n) {
for(int i=0;i<n;i++){
nums1[m+i]=nums2[i];
}
Arrays.sort(nums1);
}
}方法2：双指针 / 从前往后 一般而言，对于有序数组可以通过 双指针法 达到O(n + m)O(n+m)的时间复杂度。
最直接的算法实现是将指针p1 置为 nums1的开头， p2为 nums2的开头，在每一步将最小值放入输出数组中。
由于 nums1 是用于输出的数组，需要将nums1中的前m个元素放在其他地方，也就需要 O(m)O(m) 的空间复杂度。
class Solution {
public void merge(int[] nums1, int m, int[] nums2, int n) {
// Make a copy of nums1.
int [] nums1_copy = new int[m];
System.arraycopy(nums1, 0, nums1_copy, 0, m);
// Two get pointers for nums1_copy and nums2.
int p1 = 0;
int p2 = 0;
// Set pointer for nums1
int p = 0;
// Compare elements from nums1_copy and nums2
// and add the smallest one into nums1.
while ((p1 < m) && (p2 < n))
nums1[p++] = (nums1_copy[p1] < nums2[p2]) ? nums1_copy[p1++] : nums2[p2++];
// if there are still elements to add
if (p1 < m)
System.arraycopy(nums1_copy, p1, nums1, p1 + p2, m + n - p1 - p2);
if (p2 < n)
System.arraycopy(nums2, p2, nums1, p1 + p2, m + n - p1 - p2);
}
}复杂度分析 时间复杂度 : O(n + m)。 空间复杂度 : O(m)。
方法3 : 双指针 / 从后往前 标签：从后向前数组遍历 1.因为 nums1 的空间都集中在后面，所以从后向前处理排序的数据会更好，节省空间，一边遍历一边将值填充进去 2.设置指针 len1 和 len2 分别指向 nums1 和 nums2 的有数字尾部，从尾部值开始比较遍历，同时设置指针 len 指向 nums1 的最末尾，每次遍历比较值大小之后，则进行填充 3.当 len1<0 时遍历结束，此时 nums2 中还有数据未拷贝完全，将其直接拷贝到 nums1 的前面，最后得到结果数组 时间复杂度：O(m+n)
巧妙之处在于while ((p1 >= 0) && (p2 >= 0))采用了&符号，当跳出循环时候必然是nums1已经遍历完毕，此时直接拷贝nums2剩余的数，如果p2还大于0的话
class Solution {
public void merge(int[] nums1, int m, int[] nums2, int n) {
// two get pointers for nums1 and nums2
int p1 = m - 1;
int p2 = n - 1;
// set pointer for nums1
int p = m + n - 1;
// while there are still elements to compare
while ((p1 >= 0) & (p2 >= 0))
// compare two elements from nums1 and nums2
// and add the largest one in nums1
nums1[p--] = (nums1[p1] < nums2[p2]) ? nums2[p2--] : nums1[p1--];
// add missing elements from nums2
System.arraycopy(nums2, 0, nums1, 0, p2 + 1);
}
}腾讯云开发者
