nums1nums2mnnums1nums2
nums2nums1
nums1nums1m + nmn0nums2n
- nums1.length == m + n
- nums2.length == n
- 0 <= m, n <= 200
- 1 <= m + n <= 200
- -10 <= nums1[i], nums2[j] <= 10
O(m + n)
一开始看到这道题的时候，我就想到了是经典问题————归并排序。 就是已知两个已排序的数组，我们要将两个数组合并成一个有序的数组。 假设数组1为 nums1, 数组2为 nums2, 数组1的指针为 point1，一开始指向数组元素 nums1[0]，数组2的指针为 point2，一开始指向数组元素 nums2[0] 我们先创建一个新数组 ans，长度是 nums1 和 nums2 长度之和，用来作为答案数组，我们要做的就是遍历两个数组，对比两个指针元素，将小的元素按顺序填充到答案数组里。 主要可以分为4种情况： 1、数组1的元素小于等于数组2的元素，将数组1的元素填入答案数组，然后数组1的指针向后移动，答案数组的指针也向后移动 2、数组1的元素大于数组2的元素，将数组2的元素填入答案数组，然后数组2的指针向后移动，答案数组的指针也向后移动 3、数组1元素用完，剩下数组2的元素，直接填入答案数组即可 4、数组2元素用完，剩下数组1的元素，直接填入答案数组即可
//数组1的指针
int point1 = 0;
//数组2的指针
int point2 = 0;
//新数值的长度
int l = m+n;
int[] ans = new int[l];
for (int i = 0; i < l; i++) {
if(point1 == m){
ans[i] = nums2[point2++];
continue;
}
if (point2 == n){
ans[i] = nums1[point1++];
continue;
}
if(nums1[point1] < nums2[point2]){
//两个数组上指针上的数进行比较，如果数组1的元素小于数组2的元素，则数组1的元素填入，并且数组1的指针向后移动一位
ans[i] = nums1[point1++];
}else {
//数组1的数大于等于数组2的数，填入数组2的数，并且数组2的指针向后移动一位
ans[i] = nums2[point2++];
}
}
for (long element :
ans) {
System.out.print(element + “ ”);
}
但是，这种方法是不能通过题目的，经过几次提交验证后发现，答案是直接获取我们的数组1 nums1作为衡量标准，与返回或输出的值无关，所以我开始改变的方法，在数组1上排序，然后就突然发现一件事，由于两个数组都是已经有序的，只要一个数组填写进去完毕，剩下的自然就已经是有序的。 又是因为数组1的元素都在左边，所以我们只需要找到最大的元素，从数组后边排起，如果数组2元素用完的，那么数组直接排序完毕，不需要填充。
public static void merge(int[] nums1, int m, int[] nums2, int n) {
//要直接将数组2合并到数组1中去，不然不给通过
//可以通过数组最大的排起
int N = m+n;
//数组1的指针
int point1 = m-1;
//数组2的指针
int point2 = n-1;
for (int i = N-1; i >= 0; i–) {
//如果数组1的元素已经用完，那么不需要进行比较了，剩下的由数组2按顺序填入即可
if(point1 < 0){
nums1[i] = nums2[point2–];
continue;
}
//如果数组2的元素已经用完，那么不需要进行比较了，退出即可
if(point2 < 0){
break;
}
//从数组最大的开始比较，最大的放在数组1的最后面
if(nums1[point1] >= nums2[point2]){
//数组1的元素大于等于数组2的元素，数组1的元素移动到指定位置，并且指针大小 -1
nums1[i] = nums1[point1–];
}else if(nums1[point1] < nums2[point2]){
//数组1的元素小于数组2的元素，数组2的元素移动到指定位置，并且指针大小 -1
nums1[i] = nums2[point2–];
}
}
时间复杂度为O(m+n)
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容，请联系我们，一经查实，本站将立刻删除。
如需转载请保留出处：https://51itzy.com/kjqy/205962.html