给定两个大小分别为 和 的正序(从小到大)数组 和 。请你找出并返回这两个正序数组的 中位数 。java
时间: 2024-05-04 09:20:10 浏览: 133
求子数组最大和的解决方法详解
可以通过归并排序的思路,将两个有序数组合并成一个有序数组,然后再根据数组长度的奇偶性来确定中位数。
Java代码如下:
```java
public double findMedianSortedArrays(int[] nums1, int[] nums2) {
int m = nums1.length;
int n = nums2.length;
int[] merged = new int[m + n];
int i = 0, j = 0, k = 0;
while (i < m && j < n) {
if (nums1[i] <= nums2[j]) {
merged[k++] = nums1[i++];
} else {
merged[k++] = nums2[j++];
}
}
while (i < m) {
merged[k++] = nums1[i++];
}
while (j < n) {
merged[k++] = nums2[j++];
}
if ((m + n) % 2 == 0) {
int mid = (m + n) / 2;
return (merged[mid - 1] + merged[mid]) / 2.0;
} else {
int mid = (m + n) / 2;
return merged[mid];
}
}
```
时间复杂度为 O(m+n),其中 m 和 n 分别为两个数组的长度。
阅读全文