坚持每天刷一道题的小可爱还没有疯，依旧很可爱！
题目：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)).
Example 1： nums1 = [1, 3]，nums2 = [2]， The median is 2.0
最简单的做法，将两个数组合并，然后找中间元素。
class Solution {
public:
double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
int max = ;
int m = nums1.size() + nums2.size();
int nums[m];
int i = , j = , f = ;
while(i<nums1.size() || j<nums2.size()){
int k = (i<nums1.size()?nums1[i]:max)<=(j<nums2.size()?nums2[j]:max)?(nums1[i++]):(nums2[j++]);
nums[f++] = k;
}
float ans = m%==?((nums[m/]+nums[m/-])/2.0):(nums[(m-)/]);
return ans;
}
};
这个解法新开辟了一个新数组用来存放合并了的两个数组，空间复杂度为O（n+m）。运行时间88ms，击败7%的人。ps：果真菜。
提交过程中犯了一个小错误， float i = 3/2； // i为1.0，而不是1.5 ps：这都能忘，大概上了家里蹲大学吧。。。
刚开始用的不是数组，而是vector<int>，测试的时候显示内存超出限制，一脸懵。自己在dev上跑显示std::bad_alloc。后面才知道vector里面有一个指针指向一片连续的内存空间，当空间不够装下数据时会自动申请另一片更大的空间，然后把原有数据拷贝过去，接着释放原来的那片空间；vector的内存机制
不用新开辟数组的合并解法，不用遍历两个数组，只需要遍历两个数组总长的一半，68ms，击败30%：
class Solution {
public:
double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
int max = ;
int m = nums1.size() + nums2.size() ;
int i = , j = , f = , k, kk;
int end = m/; //m为偶数，找到m/2和m/2-1，m为奇数，找到m/2
while(f<=end){
kk = k; //用来记录m/2-1
k = (i<nums1.size()?nums1[i]:max)<=(j<nums2.size()?nums2[j]:max)?(nums1[i++]):(nums2[j++]);
f++;
cout<<k;
}
float ans = m%==?( k+kk)/2.0:k;
return ans;
}
};
继续改进：
m为nums1的长度，n为nums2的长度，若m>n，交换两个数组。寻找i、j满足1) i+j=m-i+n-j(或者m-i+n-j+1) 2) max（nums1[i-1], nums2[j-1]）<=min(nums[i],nums2[j]), 则中位数为 (max（nums1[i-1], nums2[j-1]）+min(nums1[i],nums2[j]))/2(或者min（nums1[i],nums2[j]）
寻找过程：
i = (nums1_l + nums1_r)/2 , j = (m+n)/2-i
if nums1[i-1]<=nums2[j] && nums2[j-1]<=nums1[i] 找到答案。
if nums1[i-1] > nums2[j] nums1_r = i; i应该在左半边
if nums2[i-1] < nums2[j] nums1_l = i; i应该在右半边
class Solution {
public:
double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
int n = nums1.size(), m = nums2.size();
if (n > m) {
swap(n, m);
swap(nums1, nums2);
}
int l, r, mid, pos, id = (n + m + ) / ;
l = , r = n;
while (l <= r)
{
mid = (l + r) >> ;
pos = id - mid;
if (pos >= && mid < n && nums2[pos - ] > nums1[mid]) l = mid + ;
else if (mid >= && pos < m && nums2[pos] < nums1[mid - ]) r = mid - ;
else break;
}
double ans;
if (mid == ) ans = nums2[pos - ];
else if (pos == ) ans = nums1[mid - ];
else ans = max(nums1[mid - ], nums2[pos - ]);
if ((n + m) & ) return ans;
else
{
if (mid == n) ans = (ans + nums2[pos]) / 2.0;
else if (pos == m) ans = (ans + nums1[mid]) / 2.0;
else ans = (ans + min(nums1[mid], nums2[pos])) / 2.0;
}
return ans;
}
};
时间复杂度为O（log（min（m，n）））