| java数据结构与算法刷题目录（剑指Offer、LeetCode、ACM）-----主目录-----持续更新(进不去说明我没写完)：https://blog.csdn.net/grd_java/article/details/123063846 |
|---|
我的思考过程
分别使用两个指针，作为两个数组下标然后利用归并排序的思想，左右两个数组因为有序，互相比较，填入一个数组中可以创建两个指针，正序的遍历两个数组，进行填充，但是这样需要第三个数组作为容器可以使用m和n作为指针，倒叙填充数组
代码
正序填充，时间复杂度O(m+n)
倒叙填充，时间复杂度O(m+n)
public class LeetCode88 {
public static void merge(int[] nums1, int m, int[] nums2, int n) {
int temp[] = nums1.clone();
int i = 0;
int j = 0;
int index = 0;
while(i+j=m){
nums1[index] = nums2[j];
j++;
index++;
}else if(j>=n){
nums1[index] = temp[i];
i++;
index++;
}
}
}
public static void merge2(int[] nums1, int m, int[] nums2, int n) {
int last=m+n-1;
while(n>0?true:false){
if(m==0||nums1[m-1]<=nums2[n-1]){
nums1[last--]=nums2[--n];
}else{
nums1[last--]=nums1[--m];
}
}
}
public static void main(String[] args) {
int arr[] = new int[]{4,5,6,0,0,0};
int arr2[] = new int[]{1,2,3};
merge(arr,3,arr2,3);
System.out.println(Arrays.toString(arr));
}
}
