Median of Two Sorted Arrays
题目：
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)).
题意：
给定两个已经排序的数组，找到这两个数组的中位数。时间复杂度为O(log (m+n))
思路：
先不考虑时间复杂度的要求
1.合并两个数组，排序，找到中位数即可，因为要排序，所以时间复杂度为O(nlog(n))
2.类似归并排序的其中的合并步骤，然后找到中位数即可，时间复杂度为O(m+n)
思路1代码：
class Solution {
public:
//虽然时间复杂度不满足要求，但是这段代码的确通过了- -
double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
int n = nums1.size();
nums1.resize(nums1.size()+nums2.size());
auto iter = nums1.begin() + n;
copy(nums2.begin(), nums2.end(), iter);
sort(nums1.begin(), nums1.end());
if(nums1.size()%2 == 0){
return static_cast<double>(nums1[nums1.size()/2-1] + nums1[nums1.size()/2])/2;
}else{
return nums1[nums1.size()/2];
}
}
};
思路2代码：
//要考虑的情况很多，包括数组为空，两个给定数组的顺序是小到大还是大到小，一些边界问题等等。
class Solution {
public:
double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
vector<int>nums3(nums1.size()+nums2.size());
auto iter1 = nums1.begin();
auto iter2 = nums2.begin();
//任意一个数组为空的情况
if(nums1.size() == 0){
if(nums2.size()%2 == 0){
return static_cast<double>(nums2[nums2.size()/2-1]+nums2[nums2.size()/2])/2;
}else{
return nums2[nums2.size()/2];
}
}
if(nums2.size() == 0){
if(nums1.size()%2 == 0){
return static_cast<double>(nums1[nums1.size()/2-1]+nums1[nums1.size()/2])/2;
}else{
return nums1[nums1.size()/2];
}
}
//从小到大排列的数组和从大到小排列的数组
if(*nums1.begin() < *(nums1.end()-1)){
while(iter1 != nums1.end() && iter2 != nums2.end()){
if(*iter1 < *iter2){
nums3.push_back(*iter1);
++iter1;
}else{
nums3.push_back(*iter2);
++iter2;
}
}
}else{
while(iter1 != nums1.end() && iter2 != nums2.end()){
if(*iter1 > *iter2){
nums3.push_back(*iter1);
++iter1;
}else{
nums3.push_back(*iter2);
++iter2;
}
}
}
//copy剩余的数组
if(iter1 != nums1.end()){
copy(iter1, nums1.end(), nums3.end());
}else if(iter2 != nums2.end()){
copy(iter2, nums2.end(), nums3.end());
}
int size = nums3.size();
if(size%2 == 0){
return static_cast<double>(nums3[size/2] + nums3[size/2-1])/2;
}else{
return nums3[size/2];
}
}
};重点是第三个
3.转化思维把找寻中位数变为找寻第K个最小元素，说下简化后的大致思路，两个数组，但是我们人为想像成一个数组，通过不断的 截断 我们确定的不是要找的值来缩小范围，并且缩小范围后，从寻找第k个值变为k-t那个值了，。这样的话会明显速度快，因为每次排除掉的是一小块元素而不是一个元素，有点二分的感觉，所以时间复杂度近似为O(log(m+n))吧，具体还需要证明，那么具体的做法是，假定A数组有n个元素，B数组有m个元素，我们现在要寻找中位数，设k = (n+m)/2，分别比较A[k/2]和B[k/2]两个元素，如果A[k/2] < B[k/2]，则说明中位数必定不在A[0]到A[k/2]中，那么排除掉A[0]到A[k/2]，新的数组为A[k/2]到A[n-1]，寻找的范围也就缩小了，且寻找的元素也变为第k-t个元素了，大于类似，如果等于的话就找到了第k小的数。返回即可
思路3代码:
int min(int a, int b){
return a < b ? a : b;
}
double findMedian(int *a, int n, int *b, int m, int k){
//假定a是短的数组，如果不是则交换a，b位置
if(n > m){
findMedian(b, m, a, n, k);
}
if(n == 0){
return b[k-1];
}
if(k == 1){
return min(a[0], b[0]);
}
int p = min(k/2, n), q = k-p;
//判断截取的部分
if(a[p-1] > b[q-1]){
//截取b数组，且原本寻找第k个元素变为寻找k-q个元素，进一步缩小了范围，下面类似，可以看出k在不断变化。
return findMedian(a, n, b+q, m-q, k-q);
}else if(a[p-1] < b[q-1]){
return findMedian(a+p, n-p, b, m, k-p);
}else{
return a[p-1];
}
}
double findMedianSortedArrays(int* nums1, int nums1Size, int* nums2, int nums2Size) {
int size = nums1Size + nums2Size;
if(size%2 == 0){
return findMedian(nums1, nums1Size, nums2, nums2Size, size/2+1);
}else{
return (findMedian(nums1, nums1Size, nums2, nums2Size, size/2+1) + findMedian(nums1, nums1Size, nums2, nums2Size, size/2))/2;
}
}参考博客：http://blog.csdn.net/yutianzuijin/article/details/11499917
这个题个人感觉的确比较难- -，leetcode上标记也是hard，或许我练的少吧。