解
class Solution {
public void merge(int[] nums1, int m, int[] nums2, int n) {
int[] nums3 = new int[m];
int p = 0; //指向nums3
int q = 0; //指向nums3
int place = 0; //当前选中元素存放位置
System.arraycopy(nums1, 0, nums3, 0, m);
while(p < m && q < n){
if(nums3[p] <= nums2[q]){
nums1[place++] = nums3[p++];
}else{
nums1[place++] = nums2[q++];
}
}
while(p < m){
nums1[place++] = nums3[p++];
}
while(q < n){
nums1[place++] = nums2[q++];
}
}
}
时间复杂度O(m + n) 空间复杂度 O(m)
优化解
逆序遍历
class Solution {
public void merge(int[] nums1, int m, int[] nums2, int n) {
int p = m - 1; //指向nums1尾部
int q = n - 1; //指向nums2尾部
int place = m + n - 1; //当前选中元素存放位置
while(p >= 0 && q >= 0){
if(nums1[p] < nums2[q]){
nums1[place--] = nums2[q--];
}else{
nums1[place--] = nums1[p--];
}
}
while(p >= 0){
nums1[place--] = nums1[p--];
}
while(q >= 0){
nums1[place--] = nums2[q--];
}
}
}
时间复杂度 O(m + n) 空间复杂度 O(1)