題目來(lái)源
給定兩個(gè)有序數(shù)組颠锉，求其中位數(shù)舍悯，這道題之前做過(guò)，而且在微軟面試的時(shí)候還面過(guò)。知道大概是利用二分的方法來(lái)做的横堡，但是寫代碼就是寫不出來(lái)冀泻。
然后就看了下討論區(qū)的大神做法住涉，大神們把兩個(gè)數(shù)組都填充下战惊，N個(gè)元素的數(shù)組變成2N+1長(zhǎng)度。例如1 2 3 變成# 1 # 2 # 3 #但两。
然后這樣的話不管數(shù)組是奇數(shù)還是偶數(shù)長(zhǎng)度處理起來(lái)就都一樣了鬓梅。
代碼非常簡(jiǎn)單，如下谨湘，主要是維持兩個(gè)mid绽快，使得兩個(gè)mid左邊的數(shù)目和右邊的數(shù)目一樣，然后主要看mid2悲关，就是比較短的那個(gè)串谎僻，另一個(gè)的話直接n1+n2-mid2就可以了。
然后就是l1, l2, r1, r2的維持寓辱，需要判斷一下l是否是為0以及r是否是最末尾艘绍。
注意結(jié)果應(yīng)該是double類型。
class Solution {
public:
double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
int n1 = nums1.size(), n2 = nums2.size();
if (n1 < n2)
return findMedianSortedArrays(nums2, nums1);
int lo = 0, hi = 2 * n2;
while (lo <= hi) {
int mid2 = (lo + hi) / 2;
int mid1 = n1 + n2 - mid2;
int l1 = (mid1 == 0) ? INT_MIN : nums[(mid1 - 1) / 2];
int l2 = (mid2 == 0) ? INT_MIN : nums[(mid2 - 1) / 2];
int r1 = (mid1 == n1 * 2) ? INT_MAX : nums[mid1 / 2];
int r2 = (mid2 == n2 * 2) ? INT_MAX : nums[mid2 / 2];
if (l1 > r2)
lo = mid1 + 1;
else if (l2 > r1)
hi = mid1 - 1;
else
return (max(l1, l2) + min(r1, r2)) / 2;
}
return -1;
}
};
