給定兩個大小為 m 和 n 的正序（從小到大）數(shù)組 nums1 和 nums2淆九。
請你找出這兩個正序數(shù)組的中位數(shù)，并且要求算法的時間復(fù)雜度為 O(log(m + n))毛俏。
你可以假設(shè) nums1 和 nums2 不會同時為空炭庙。
示例 1:
nums1 = [1, 3]
nums2 = [2]
則中位數(shù)是 2.0
示例 2:
nums1 = [1, 2]
nums2 = [3, 4]
則中位數(shù)是 (2 + 3)/2 = 2.5
通過次數(shù)186,773提交次數(shù)498,918
public double findMedianSortedArrays(int[] nums1, int[] nums2) {
int len = nums1.length + nums2.length;
if (len % 2 == 0) {
return ((double) findKth(nums1, 0, nums2, 0, len / 2) + (double) findKth(nums1, 0, nums2, 0, len / 2 + 1)) / 2;
}
return findKth(nums1, 0, nums2, 0, (len + 1) / 2);
}
public int findKth(int[] nums1, int left1, int[] nums2, int left2, int k) {
// 如果其中一個arr已經(jīng)刪完了，那么只用刪另一個arr就行
if (left1 >= nums1.length) return nums2[left2 + k - 1];
if (left2 >= nums2.length) return nums1[left1 + k - 1];
if (k == 1) return Math.min(nums1[left1], nums2[left2]);
// 當(dāng)一個arr特別短煌寇，不夠用時煤搜，那么只刪另一個arr即可（用MAX_VALUE保證不會被刪除，因?yàn)?誰小刪誰"）
int mid1 = left1 + k / 2 - 1 < nums1.length ? nums1[left1 + k / 2 - 1] : Integer.MAX_VALUE;
int mid2 = left2 + k / 2 - 1 < nums2.length ? nums2[left2 + k / 2 - 1] : Integer.MAX_VALUE;
if (mid1 <= mid2) {
return findKth(nums1, left1 + k / 2, nums2, left2, k - k / 2);
}
return findKth(nums1, left1, nums2, left2 + k / 2, k - k / 2);
}
