合并两个有序数组
题目:
思路:
解法有两种:
1,顺序排序,需要额外创建一个数组大小为m+n,然后比较A与B,遍历填充进新数组。然后把数组再次填充回A里面,所以次数为2*(m+n),当m+n趋于无穷大时,2就被忽略了,时间复杂度为O(m+n),空间复杂度为O(m+n)
2,对于第一种方法如果要优化的点可以从空间开始,因为题目本身就是给予了A足够大的空间,其次是多次额外的赋值对于操作来说也是浪费,所以可以考虑倒序排序的思路。
这种方法的时间复杂度为O(m+n),空间复杂度为O(1)。
代码示例:
import java.util.Arrays;
public class Solution {
public static void main(String[] args) {
int[] arr1 = new int[20];
int[] arr2 = new int[10];
int k = 0;
for (int i = 0; i < 20; i++) {
if (i % 2 == 0) {
arr1[i / 2] = i;
} else {
arr2[i / 2] = i;
}
}
// System.out.println(Arrays.toString(arr1));
// System.out.println(Arrays.toString(arr2));
int n = arr2.length;
int m = arr1.length - n;
merge(arr1, m, arr2, n);
System.out.println(Arrays.toString(arr1));
}
/**
* 为什么是从倒序开始呢?因为从前面开始排,你比对完后占了位置,其他数就要往后面移动,这样操作太大
* 而且从前文可知A的大小足够容纳两个数组的数,所以从后面按大到小进行排序,这样不会造成其他数因为某个数而需要往后靠的操作
* 同理需要注意的是下面缺少了对a的继续遍历,因为A数组本身就是有序的,所以如果第一个循环中把a遍历到了最小值,此时要把b继续遍历完
* 而如果b遍历完了,那么a大可不必遍历,因为本身有序,且是在A里面
*/
public static void merge(int A[], int m, int B[], int n) {
int a = m - 1;
int b = n - 1;
int k = m + n - 1;
while (a >= 0 && b >= 0) {
A[k--] = A[a] > B[b] ? A[a--] : B[b--];
}
while (b >= 0) {
A[k--] = B[b--];
}
}
}
相关文章
- Java8数组和List相互转换
- js数组常用方法「建议收藏」
- 日拱算法:两个数组的交集(I、II)
- LeetCode 88. 合并两个有序数组
- JavaScript 数组
- 剑指offer之找出数组中重复的数字
- 4. 两个排序数组的中位数
- 【力扣刷题】4. 寻找两个正序数组的中位数
- 2022-12-08:给定n棵树,和两个长度为n的数组a和b i号棵树的初始重量为a[i],i号树每天的增长重量为b[i] 你每天最多能砍1棵树,这天收益 =
- 数据结构001:最大子数组和
- 2022-11-28:给定两个数组A和B,比如 A = { 0, 1, 1 } B = { 1, 2, 3 } A[0] = 0
- leetcode:合并两个有序数组
- 【嵌入式开发】C语言 指针数组 多维数组
- 【C 语言】数组 ( 指针退化验证 | 计算数组大小 | #define LENGTH(array) (sizeof(array) / sizeof(*array)) )
- 每日一道leetcode:4. 寻找两个正序数组的中位数
- 力扣——寻找两个正序数组的中位数
- 【力扣/牛客刷题】27. 移除元素 || 26. 删除有序数组中的重复项 || 88. 合并两个有序数组
- 算法-寻找两个正序数组的中位数
- python获得两个数组的交集、并集、差集详解编程语言
- PHP操作 二维数组模拟mysql函数详解编程语言
- C++数组初始化方法详解
- C++比较两个数组是否相等(详解版)
- php数组应用之比较两个时间的相减排序
- js取两个数组的交集|差集|并集|补集|去重示例代码
- 两个数组去重的JS代码