一、题目
二、解题
注:本文均是Java代码
1、合并后排序
class Solution {
public void merge(int[] nums1, int m, int[] nums2, int n) {
// 时间复杂度O(m+n)*log(m+n)
// 空间复杂度O(1)
System.arraycopy(nums2,0,nums1,m,n);
Arrays.sort(nums1);
}
}
2、双指针(从前往后)
class Solution {
public void merge(int[] nums1, int m, int[] nums2, int n) {
// 时间复杂度O(m+n)
// 空间复杂度O(m)
int[] nums1_copy = new int[m];
System.arraycopy(nums1,0,nums1_copy,0,m);
int p1 = 0 , p2 = 0, p = 0;
while (p1 < m && p2 < n) {
nums1[p++] = (nums1_copy[p1] < nums2[p2] ? nums1_copy[p1++] : nums2[p2++]);
}
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);
}
}
3、双指针(从后往前)
class Solution {
public void merge(int[] nums1, int m, int[] nums2, int n) {
// 时间复杂度O(m+n)
// 空间复杂度O(1)
int p = m + n - 1;
int p1 = m - 1;
int p2 = n - 1;
while (p1 >= 0 && p2 >= 0) {
nums1[p--] = (nums1[p1] < nums2[p2] ? nums2[p2--] : nums1[p1--]);
}
while (p2 >= 0) nums1[p--] = nums2[p2--];
}
}