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)).
Example 1:
nums1 = [1, 3] nums2 = [2] The median is 2.0
Example 2:
nums1 = [1, 2] nums2 = [3, 4] The median is (2 + 3)/2 = 2.5 两个升序的数组，求它们所有元素的中位数，要求复杂度为O（log （m+n））。。。。。。完全不会，只会一个一个的递进比较大小，最坏情况下复杂度O(m+n)
参考的网上的解法
题目的一般形式为两个升序排列的数组，找出他们中第K大的元素
思路，类似于二分
假设nums1和muns2中的元素个数都大于K/2，将nums1和nums2中的第K/2个元素比较大小
则有三种情况
1.nums1[K / 2 - 1] > nums2[K / 2 - 1]
2.nums1[K / 2 - 1] = nums2[K / 2 - 1]
3.nums1[K / 2 - 1] < nums2[K / 2 - 1]
第一种情况,我们可以确定nums2中的前K/2个元素一定比我们要找的第K大的数小，可以除去
第二种情况,那么nums1和nums2中的第K/2个元素就是我们要找的第K大元素
第三种情况,我们可以确定nums1中的前K/2个元素一定比我们要找的第K大的数小，可以除去
因此我们可以写一个递归函数，终止条件
1.nums1或nums2为空，则返回nums1[K - 1]或nums2[K - 1]
2.K = 1时，返回返回min(nums1[1],nums2[1])
3.nums1[K / 2 - 1] = nums2[K / 2 - 1]返回两者中一个
AC解
class Solution { public: double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) { int m = nums1.size(); int n = nums2.size(); int total = m + n; if (total & 0x1) //奇数 return findKth(nums1.begin(),m,nums2.begin(),n,total / 2 + 1); else return (findKth(nums1.begin(),m,nums2.begin(),n,total / 2) + findKth(nums1.begin(),m,nums2.begin(),n,total / 2 + 1)) / 2.0; } int findKth(std::vector<int>::const_iterator it_nums1,int m ,std::vector<int>::const_iterator it_nums2,int n ,int K) { if (m > n) return findKth(it_nums2,n,it_nums1,m,K);//始终使前面一个容器元素个数少 if (m == 0) return *(it_nums2 + K - 1); if (K == 1) return min(*it_nums1,*it_nums2); int i = min(m ,K / 2),j = K - i; if (*(it_nums1 + i - 1) > *(it_nums2 + j - 1)) return findKth(it_nums1,m,it_nums2 + j,n - j,K - j); else if (*(it_nums1 + i - 1) < *(it_nums2 + j - 1)) return findKth(it_nums1 + i,m - i,it_nums2,n,K - i); else return *(it_nums1 + i - 1); } };
