Median of Two Sorted Arrays - 每日算法
每日算法——letcode系列
问题 Median of Two Sorted Arrays
Difficulty: Hard
There are two sorted arrays nums1 and nums2 of size m and n respectively. Find the median of the two sorted arrays. The overall run time complexity should be O(log (m+n)).
class Solution {public: double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {}};翻译
两个有序数组的中位数
难度系数：困难
有两个大小分别为m和n的 nums1和nums2有序数组。 找出这两个有序数组的中位数。 时间复杂度应为$O(log (m+n))$.
思路
先转化成topK问题，再分两种情况：
m + n为奇数时，返回第K就好
m + n为偶数时，返回第K和K + 1的平均值
由于题目要求是O(log(m+n))时间复杂度，那必须得用有序的信息，想到二分法，总想把两数组各减一半最好，但这种可能把中位数也剔除了，
如：
[1, 2, 5, 6] -> [5, 6]
[3, 4, 7, 8] -> [7, 8] 这样就把中位数4给剔除了，但可以得用一点，上面个数组中的[1, 2]是可以剔除的。两长度分别为m, n的数组A, B，假设k = $\frac{（m + n) }{2}$ 。
将k分成两成pa,pb两部分，由于是两个数组，长度不一致，为不越界，有两种分法：（假设m>n）
当$\frac{k}{2}$ $\leq$n时， 直接分成pa = pa = $\frac{k}{2}$
当$\frac{k}{2}$ > n时, pa = n, pb = k - pa
下面分析当$\frac{k}{2}$ $\leq$n的三种情况
A[$\frac{k}{2}$] == B[$\frac{k}{2}$]
A[$\frac{k}{2}$] > B[$\frac{k}{2}$]
A[$\frac{k}{2}$] < B[$\frac{k}{2}$]
第一种情况：
如果将B合并到A，那么B[0]到B[$\frac{k}{2}$-1]肯定在A的左边， B[$\frac{k}{2}$+1]到B[n]肯定放在A的右边，那中位数即为A[$\frac{k}{2}$]、B[$\frac{k}{2}$]第二种情况：
如果：中位数在B[0]到B[$\frac{k}{2}$]中， 假设中位数的索引为mid。
那么B[0] $\leq$B[mid] $\leq$B[$\frac{k}{2}$]， 则B中至少有n - $\frac{k}{2}$个在B[mid] 右边
由于A[$\frac{k}{2}$] > B[$\frac{k}{2}$]， 则A中至少有m - $\frac{k}{2}$ + 1个在B[mid] 右边
则至少有n - $\frac{k}{2}$ + m - $\frac{k}{2}$ + 1 = k + 1个数在B[mid]的右边, 则当且仅当mid = $\frac{k}{2}$满足要求， 比如A = [6], B = [1, 2, 8]，如果A[$\frac{k}{2}$ -1] > B[$\frac{k}{2}$ -1]呢？
同上分析得：则至少有n - （$\frac{k}{2}$ -1) + m - ($\frac{k}{2}$-1) + 1 = k + 3> k+1个数在B[mid]的右边, 则中位数肯定不在B[0]到B[$\frac{k}{2}$ -1]中，可剔除
第三种情况同第二种类似：当A[$\frac{k}{2}$ -1] < B[$\frac{k}{2}$ -1]中位数肯定不在A[0]到A[$\frac{k}{2}$ -1]中。
由上分析可得：
A[$\frac{k}{2}$-1] == B[$\frac{k}{2}$-1时：A[$\frac{k}{2}$-1]、 B[$\frac{k}{2}$-1]为中位数
A[$\frac{k}{2}$-1] > B[$\frac{k}{2}$-1]时：中位数肯定不在B[0]到B[$\frac{k}{2}$-1]中
A[$\frac{k}{2}$-1] < B[$\frac{k}{2}$-1]时：中位数肯定不在A[0]到A[$\frac{k}{2}$-1]中
则我们可以递归的剔除二个数组中的一些数
中止条件：
当A[$\frac{k}{2}$-1] == B[$\frac{k}{2}$-1时，返回其中一个
当A、B中一个为空时， 分别返回B[k-1]或A[k-1]
当k = 1时， 返回A[0]、B[0]中小的一个
当$\frac{k}{2}$ > n时, 也是同样的分析方法
代码
//// main.cpp// Median of Two Sorted Arrays//// Created by zhz on 15/12/15.// Copyright (c) 2015年 zhz. All rights reserved.//#include <iostream>#include <vector>using namespace std;class Solution {public: double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) { int m = static_cast<int>(nums1.size()); int n = static_cast<int>(nums2.size()); int k = (m + n + 1) / 2; if ((m + n) % 2 != 0){return findKthBigNum(nums1, nums2, k); } else{return (findKthBigNum(nums1, nums2, k + 1) + findKthBigNum(nums1, nums2, k)) / 2.0; }} private: double findKthBigNum(vector<int>& nums1, vector<int>& nums2, int k){ int m = static_cast<int>(nums1.size()); int n = static_cast<int>(nums2.size()); if (n > m){return findKthBigNum(nums2, nums1, k); } if (n == 0){return nums1[k - 1]; } if (k == 1){return nums1[0] < nums2[0] ? nums1[0] : nums2[0]; } int pa = min(k / 2, n), pb = k - pa; if (nums1[pb - 1] == nums2[pa - 1]){return nums2[pa - 1]; } else if (nums1[pb - 1] > nums2[pa - 1]) {vector<int> tempNums;if (pa <= nums2.size()){ tempNums.assign(nums2.begin() + pa, nums2.end()); k = k - pa;}else{ k = k - static_cast<int>(nums2.size());}return findKthBigNum(nums1, tempNums, k); } else {vector<int> tempNums;if (pb <= nums1.size()){ tempNums.assign(nums1.begin() + pb, nums1.end()); k = k - pb;}else{ k = k - static_cast<int>(nums1.size());} return findKthBigNum(tempNums, nums2, k); } }};int main(int argc, const char * argv[]) { vector<int> nums1 = {3}; vector<int> nums2 = {1, 2, 4}; auto s = new Solution(); double mid = s->findMedianSortedArrays(nums1, nums2); std::cout << "Hello, World!\n"; return 0;}后记： 代码的实现有很多细节活，一定要多练，不能光靠想