题目描述
整理一下思路,可以只对第一个数组进行划分,如果知道第一个的划分就可以知道第二个元素怎么划分的了,
需要注意的是:
- 1.记录第一个数组划分的位置cut1左右的值L1和R1, 和第二个的划分cut2的左右元素值L2和R2.
- 2.如果L1>R2,那么cut1需要左移,如果L2>R1说明cut1需要右移动.否则说明划分成功.
- 3.如果为偶数个,那么中值是左边:max(L1, L2), 右边是:min(R1, R2).
- 4.如果是奇数个,那么就是:min(R1, R2).
C++ 代码
/*
L1 R1
nums1: 3 5 | 8 9
L2 R2
nums2: 1 2 7 | 10 11 12
nums : 1 2 3 5 7 | 8 9 10 11 12
L1: cut1分割点左边的元素值
条件: L1 < R2
L2 < R1
L1 > R2 cut1左移
L2 > R1 cut1右边移动
int cut1: 表示nums1分割点左边有多少个元素。
int cut2: 表示nums2分割点左边元素个数.
int cutL: 表示nums1二分的左端点。
int cutR: nums1二分右端点.
*/
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 len = n1 + n2;
int cut1 = 0; //nums1分割点左边元素个数.
int cut2 = 0; // nums2分割点左边元素个数.
int cutL = 0; //对nums1进行二分的左端点.
int cutR = n1; //对nums1进行二分的右端点.
while (cut1 <= n1) {
cut1 = (cutR - cutL) / 2 + cutL;
cut2 = len / 2 - cut1;
double L1 = (cut1 == 0) ? INT_MIN : nums1[cut1 - 1]; //如果左边没有元素设置L1 = INT_MIN, 保证L1<R2.
double L2 = (cut2 == 0) ? INT_MIN : nums2[cut2 - 1]; //if : L2 = INT_MIN < R1
double R1 = (cut1 == n1) ? INT_MAX : nums1[cut1]; //if : R1 = INT_MAX > L2
double R2 = (cut2 == n2) ? INT_MAX : nums2[cut2];
if (L1 > R2) {
cutR = cut1 - 1; // 分割点需要左移动。
}
else if (L2 > R1) {
cutL = cut1 + 1; // 分割点需要右边移动。
}
else {
if (len % 2 == 0) {
L1 = L1 > L2 ? L1 : L2; //选择左边较大的
R1 = R1 < R2 ? R1 : R2; //和右边较小的。
return (L1 + R1) / 2;
}
else {
R1 = R1 < R2 ? R1 : R2; //偶数的话是右边较小的元素。
return R1;
}
}
}
return -1;
}
};