2019-03-17 Median of Two Sorted
暴力算法就是从两个数组开端开始扫描，知道index为中间的一个或者两个数，取得结果，代码如下：
class Solution {
public:
double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
int smaller;
int lastSmaller;
int currentIndex = 0;
int middle = (nums1.size() + nums2.size()) / 2;
bool odd = (nums1.size() + nums2.size()) % 2 == 0;
int i1 = 0; int i2 = 0;
while (currentIndex <= middle) {
lastSmaller = smaller;
if (i1 < nums1.size() && i2 < nums2.size()) {
int n1 = nums1.at(i1);
int n2 = nums2.at(i2);
if (n1 < n2) {
smaller = n1;
i1++;
} else {
smaller = n2;
i2++;
}
} else if (i1 >= nums1.size() && i2 < nums2.size()) {
smaller = nums2.at(i2);
i2++;
} else if (i1 <= nums1.size() && i2 >= nums2.size()) {
smaller = nums1.at(i1);
i1++;
} else {
throw "error!";
}
currentIndex++;
}
if (!odd) {
return smaller;
} else {
return ((float)smaller + (float)lastSmaller) / 2;
}
}
};
方案二：
看了别人的博客，主要的点子就是转化为求第K大的数的问题，然后利用已排序的性质，做类似二分法的查找。比如有两个已排序数组，A,B。我们要求第K大的数。
我们可以直接比较A[K/2],B[K/2]，分情况讨论如下：
2-1、A长度小于K/2,那肯定第K大的数在B中，具体为B[K - A.length - 1]
2-2、B长度小于K/2，那肯定第K大的数在A中，具体为A[K - B.length -1]
2-3、A[K/2] > B[K/2]，那么B[K/2]之前的数肯定都比A[K/2]小。我们可以直接去掉这一部分（假设这部分长度为pb)，则继续从A,B'（B'为B去掉前pb个数剩下的数组）找第K-pb大的数
2-4、同理，如果反过来的结果，则从A从去除一部分数，然后继续递归求结果
2-5、如果A[K/2]=B[K/2]，则说明 A[K/2]就是第K大的数，直接返回（A[K/2]前面有K/2-1个数，B也一样，所以A[K/2]就是第K/2以及K/2-1个数
class Solution {
public:
double find(int *a, int n, int *b, int m, int k) {
if (n > m) return find(b, m, a, n, k);
else if (n == 0) return b[k - 1];
else if (k == 1) return min(a[0], b[0]);
int pa = min(k/2, n), pb = k - pa;
int diff = a[pa - 1] - b[pb - 1];
if (diff == 0) return a[pa - 1];
else if (diff < 0) return find(a + pa, n - pa, b, m, k - pa);
else return find(a, n, b + pb, m - pb, k - pb);
}
double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
int total = nums1.size() + nums2.size();
if (total & 1) {
return find(nums1.data(), nums1.size(), nums2.data(), nums2.size(), total / 2 + 1);
} else {
return (find(nums1.data(), nums1.size(), nums2.data(), nums2.size(), total / 2 + 1)
+ find(nums1.data(), nums1.size(), nums2.data(), nums2.size(), total / 2) ) / 2;
}
}
};
