用java做一道算法题:给定两个大小分别为 m 和 n 的正序(从小到大)数组 nums1 和 nums2。请你找出并返回这两个正序数组的 中位数 。 算法的时间复杂度应该为 O(log (m+n)) 。
时间: 2024-05-07 20:22:38 浏览: 167
寻找两个正序数组的中位数 .md
这道题可以使用二分查找算法来解决。我们需要将两个数组合并成一个有序的数组,然后找到这个有序数组的中位数。具体步骤如下:
1. 定义两个指针 i 和 j,分别指向 nums1 和 nums2 的起始位置。
2. 使用二分查找算法查找有序数组中的中位数。我们需要将查找的范围缩小到两个数组的中间位置左右。
3. 如果 nums1[i] < nums2[j],说明中位数在 nums1[i] 和 nums2[j] 之间。我们将 i 向右移动一位,缩小查找范围。
4. 如果 nums1[i] >= nums2[j],说明中位数在 nums1[i] 和 nums2[j] 之间。我们将 j 向右移动一位,缩小查找范围。
5. 重复步骤 2 到 4,直到找到中位数。
Java 代码实现如下:
```java
public double findMedianSortedArrays(int[] nums1, int[] nums2) {
int m = nums1.length;
int n = nums2.length;
if (m > n) {
// 保证 nums1 的长度小于等于 nums2 的长度
int[] temp = nums1;
nums1 = nums2;
nums2 = temp;
int tmp = m;
m = n;
n = tmp;
}
int iMin = 0, iMax = m, halfLen = (m + n + 1) / 2;
while (iMin <= iMax) {
int i = (iMin + iMax) / 2;
int j = halfLen - i;
if (i < iMax && nums2[j-1] > nums1[i]){
iMin = i + 1; // i is too small
}
else if (i > iMin && nums1[i-1] > nums2[j]) {
iMax = i - 1; // i is too big
}
else { // i is perfect
int maxLeft = 0;
if (i == 0) { maxLeft = nums2[j-1]; }
else if (j == 0) { maxLeft = nums1[i-1]; }
else { maxLeft = Math.max(nums1[i-1], nums2[j-1]); }
if ( (m + n) % 2 == 1 ) { return maxLeft; }
int minRight = 0;
if (i == m) { minRight = nums2[j]; }
else if (j == n) { minRight = nums1[i]; }
else { minRight = Math.min(nums2[j], nums1[i]); }
return (maxLeft + minRight) / 2.0;
}
}
return 0.0;
}
```
时间复杂度为 O(log(min(m, n)))。
阅读全文