给定两个大小分别为 m 和 n 的正序(从小到大)数组 nums1 和 nums2。请你找出并返回这两个正序数组的 中位数 。 算法的时间复杂度应该为 O(log (m+n)) 。 java代码
时间: 2024-09-28 16:05:32 浏览: 37
为了找到两个有序数组 `nums1` 和 `nums2` 的中位数,我们可以采用分治法的思想。由于题目要求时间复杂度为 `O(log(m+n))`,我们不需要遍历整个数组,而是采用二分查找的方式。下面是 Java 代码实现:
```java
public double findMedianSortedArrays(int[] nums1, int[] nums2) {
// 合并两个数组,并排序
Arrays.sort(nums1);
Arrays.sort(nums2);
// 获取合并数组的长度
int m = nums1.length;
int n = nums2.length;
if (m == n) { // 如果两个数组长度相等,直接取中间值
return (double)(nums1[m - 1] + nums2[0]) / 2;
} else if (m > n) { // 如果 nums1 更长
return findKthSmallest(nums1, nums2, m + n / 2);
} else { // 如果 nums2 更长
return findKthSmallest(nums2, nums1, m + n / 2);
}
}
private int findKthSmallest(int[] nums1, int[] nums2, int k) {
int left = 0, right = Math.min(nums1.length, nums2.length); // 分界点
while (left <= right) {
int partitionNums1 = nums1[left];
int partitionNums2 = nums2[right];
if (k == (partitionNums1 + partitionNums2 + 1) / 2) { // 如果是中间位置
return partitionNums1;
} else if (partitionNums1 + nums1.length < k) { // 如果 k 在左边数组的右边
left++;
} else { // 如果 k 在右边数组的左边
right--;
}
}
throw new IllegalArgumentException("Array is too small to find the kth smallest element.");
}
```
在这个代码中,`findKthSmallest` 函数用于查找合并数组的第 `k` 小元素。通过不断调整左右边界,直到找到正确的索引 `k`,然后返回该位置的值作为中位数。因为数组已经排序,所以二分查找可以在对数时间内完成。
阅读全文