帮我写一段代码:给定两个大小分别为 m 和 n 的正序(从小到大)数组 nums1 和 nums2。请你找出并返回这两个正序数组的中位数。算法的时间复杂度应该为 O(log (m+n))
时间: 2023-03-15 15:02:22 浏览: 123
python-leetcode面试题解之寻找两个正序数组的中位数.zip
class Solution {
public double findMedianSortedArrays(int[] nums1, int[] nums2) {
int m = nums1.length;
int n = nums2.length;
int left = (m + n + 1) / 2;
int right = (m + n + 2) / 2;
return (helper(nums1, 0, m - 1, nums2, 0, n - 1, left) + helper(nums1, 0, m - 1, nums2, 0, n - 1, right)) / 2.0;
}
public double helper(int[] nums1, int start1, int end1, int[] nums2, int start2, int end2, int k) {
int len1 = end1 - start1 + 1;
int len2 = end2 - start2 + 1;
if(len1 == 0) {
return nums2[start2 + k - 1];
} else if(len2 == 0) {
return nums1[start1 + k - 1];
}
if(k == 1) {
return Math.min(nums1[start1], nums2[start2]);
}
int i = start1 + Math.min(len1, k/2) - 1;
int j = start2 + Math.min(len2, k/2) - 1;
if(nums1[i] > nums2[j]) {
return helper(nums1, start1, end1, nums2, j + 1, end2, k - (j - start2 + 1));
} else {
return helper(nums1, i + 1, end1, nums2, start2, end2, k - (i - start1 + 1));
}
}
}
阅读全文