染得道家衣
淡妆梳洗时
晓来清露滴
C++，二分，这道题我看到复杂度要求就知道是二分了，但是依然想了很久才知道大概的理论，然后代码实践又是一个下午。。。菜得真实。
本题的理论就是在短序列A1中找到一个分界下标点m1，其满足如下条件（短长序列长度分别为len1, len2）：
- 可以在短序列A2找到一个唯一的m2，满足：
- 如果
(len1 + len2) % 2 == 0，则(m1 + m2) * 2 == len1 + len2 - 如果
(len1 + len2) % 2 == 1，则(m1 + m2) * 2 == len1 + len2 + 1
- 如果
- m1和m2分别满足：
A1[m1] <= A2[m2 + 1]A2[m2] <= A1[m1 + 1]
用人话说就是：分别分割序列A1和A2，[A1的前序列，A2的前序列] <= [A1的后序列，A2的后序列]，该<=对于组合序列中的任意元素都满足。
而我们的二分就是在短序列中找到这么一个m1，m1满足以上两个条件即可。
具体的话，题解中讲解的比较细致，这里不再赘述。
需要注意的有两个特殊的情况：
- 短序列可能找不到这样的m1，可能是因为A1的所有所有元素都划分为后序列，即全部在中位数之后
- 短序列没有元素，即长度为0
代码写起来也是比较麻烦的，发现二分都是想起来简单，写起来麻烦2333。
class Solution {
public:
double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
if (nums1.size() > nums2.size())
swap(nums1, nums2);
int len1 = nums1.size();
int len2 = nums2.size();
int len = len1 + len2;
if (len1 == 0) {
if (len % 2 == 0)
return (nums2[len2 / 2] + nums2[len2 / 2 - 1]) / 2.0;
else
return nums2[len2 / 2];
}
int left = 0, right = len1 - 1;
while (left <= right) {
int mid1 = (left + right) / 2;
int mid2 = len % 2 == 0 ? \
(len / 2 - mid1 - 2) : (len / 2 - mid1 - 1);
int rightmin1 = (mid1 + 1 >= len1) ? INT_MAX : nums1[mid1 + 1];
int rightmin2 = (mid2 + 1 >= len2) ? INT_MAX : nums2[mid2 + 1];
if (nums1[mid1] > rightmin2)
right = mid1 - 1;
else if (mid2 >= 0 && nums2[mid2] > rightmin1)
left = mid1 + 1;
else {
int maxmid = 0;
if (mid2 < 0)
maxmid = nums1[mid1];
else
maxmid = max(nums1[mid1], nums2[mid2]);
if (len % 2 == 0) {
return ((double)maxmid + min(rightmin1, rightmin2)) / 2;
} else return maxmid;
}
}
// 如果没找到这么一个分界点，说明nums1序列无法被分割
if (len % 2 == 0) {
int mid = len / 2 - 1;
int leftmax = nums2[mid];
int rightmin = nums1[0];
rightmin = mid + 1 < len2 ? min(nums2[mid + 1], rightmin) : rightmin;
return (leftmax + rightmin) / 2.0;
} else return nums2[len / 2];
}
};
