leetcode4. 寻找两个有序数组的中位数
5星 · 超过95%的资源 107 浏览量
2021-01-06
22:40:30
上传
评论
收藏 24KB PDF 举报 
leetcode4. 寻找两个有序数组的中位数寻找两个有序数组的中位数
/* 1.暴力合并，用一个新数组来存放时间和空间都是O(m+n)
2.还是暴力法，不过不用新数组，而是用两个指针和一个变量来求第k小的数，k=(m+n)/2
3.用二分法来求第k小的数，如果m+n是偶数，则求第k和第k+1小的平均值。
*/
class Solution {
public double findMedianSortedArrays(int[] nums1, int[] nums2) {
int n = nums1.length;
int m = nums2.length;
int left = (n + m + 1) / 2;
int right = (n + m + 2) / 2;
//解决了两个数组中位数有一个或者两个的问题
return (getKth(nums1, 0, n - 1, nums2, 0, m - 1, left) + getKth(nums1, 0, n - 1, nums2, 0, m - 1, right)) * 0.5;
}
//该函数只求第k小的数
private int getKth(int[] nums1, int start1, int end1, int[] nums2, int start2, int end2, int k) {
int len1 = end1 - start1 + 1;
int len2 = end2 - start2 + 1;
//让len1长度小于len2，如果有空数组则一定是len1
if (len1 > len2)
return getKth(nums2, start2, end2, nums1, start1, end1, k);
if (len1 == 0)
return nums2[start2 + 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 getKth(nums1, start1, end1, nums2, j + 1, end2, k - (j - start2 + 1));
} else {
return getKth(nums1, i + 1, end1, nums2, start2, end2, k - (i - start1 + 1));
}
}
}
作者：wl1929
评论10
最新资源