做leetcode题目的第二天，我是按照分类来做的，做的第一类是Array类，碰见的第二道题目，也就是今天做的这个，题目难度为hard。题目不难理解，但是要求到了时间复杂度，就需要好好考虑使用一下算法了。刚开始没啥思路，就用暴力的方法，用双层循环遍历的一下两个已经排好序的数组 ，在中间位置停止找道中位数。这样时间复杂度是肯定不能满足题目要求的，但是程序测试还是过了。
苦于自己没有思路，又不甘心就这样水过一道题，还是搜了一下博客，膜拜了一下大神。最好的方法是将中位数 -- 两个数组数据排好序之后的（m+n）/2 位置左右的数（奇，偶）（程序里面会有体现）--看成是求排好序的数组的第k = (m+n)/2 小的数据，然后采用类似于二分的方法求解。
在这里先把题目粘过来：
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:
1 nums1 = [1, 3] 2 nums2 = [2] 3 4 The median is 2.0
Example 2:
1 nums1 = [1, 2] 2 nums2 = [3, 4] 3 4 The median is (2 + 3)/2 = 2.5
这里先把我的java代码贴一下：（给自己个警示）
1 public class Solution { 2 public double findMedianSortedArrays(int[] nums1, int[] nums2) { 3 int len = nums1.length+nums2.length; 4 int []ans_c = new int[len]; 5 boolean flag = false; 6 int i=0,j=0; 7 int k=0; 8 for(;k<len/2+1;k++){ 9 if(i<nums1.length && j<nums2.length){ 10 if(nums1[i]<=nums2[j]){ 11 ans_c[k]=nums1[i]; 12 i++; 13 } 14 else{ 15 ans_c[k]=nums2[j]; 16 j++; 17 } 18 } 19 else if(i<nums1.length){ 20 ans_c[k]=nums1[i]; 21 i++; 22 } 23 else{ 24 ans_c[k]=nums2[j]; 25 j++; 26 } 27 } 28 if(len%2==0){ 29 return (double)(ans_c[k-1]+ans_c[k-2])/2; 30 } 31 else{ 32 return (double)ans_c[k-1]; 33 } 34 } 35 }
C++ 代码：
这里对于求解思路呢我就不做过多的说明了，把别人的博客链接发过来自己欣赏一下吧，我想做的是对自己写的代码进行一下注释说明，以便自己之后回忆起来好理解。
这里摘录一下他的分析过程
1 最后从medianof two sorted arrays中看到了一种非常好的方法。原文用英文进行解释，在此我们将其翻译成汉语。该方法的核心是将原问题转变成一个寻找第k小数的问题（假设两个原序列升序排列），这样中位数实际上是第(m+n)/2小的数。所以只要解决了第k小数的问题，原问题也得以解决。 2 3 首先假设数组A和B的元素个数都大于k/2，我们比较A[k/2-1]和B[k/2-1]两个元素，这两个元素分别表示A的第k/2小的元素和B的第k/2小的元素。这两个元素比较共有三种情况：>、<和=。如果A[k/2-1]<B[k/2-1]，这表示A[0]到A[k/2-1]的元素都在A和B合并之后的前k小的元素中。换句话说，A[k/2-1]不可能大于两数组合并之后的第k小值，所以我们可以将其抛弃。 4 5 证明也很简单，可以采用反证法。假设A[k/2-1]大于合并之后的第k小值，我们不妨假定其为第（k+1）小值。由于A[k/2-1]小于B[k/2-1]，所以B[k/2-1]至少是第（k+2）小值。但实际上，在A中至多存在k/2-1个元素小于A[k/2-1]，B中也至多存在k/2-1个元素小于A[k/2-1]，所以小于A[k/2-1]的元素个数至多有k/2+ k/2-2，小于k，这与A[k/2-1]是第（k+1）的数矛盾。 6 7 当A[k/2-1]>B[k/2-1]时存在类似的结论。 8 9 当A[k/2-1]=B[k/2-1]时，我们已经找到了第k小的数，也即这个相等的元素，我们将其记为m。由于在A和B中分别有k/2-1个元素小于m，所以m即是第k小的数。(这里可能有人会有疑问，如果k为奇数，则m不是中位数。这里是进行了理想化考虑，在实际代码中略有不同，是先求k/2，然后利用k-k/2获得另一个数。) 10 11 通过上面的分析，我们即可以采用递归的方式实现寻找第k小的数。此外我们还需要考虑几个边界条件： 12 13 如果A或者B为空，则直接返回B[k-1]或者A[k-1]； 14 如果k为1，我们只需要返回A[0]和B[0]中的较小值； 15 如果A[k/2-1]=B[k/2-1]，返回其中一个；
这里我补充说明几个问题：
第一是两个数组长度之和是有奇、偶之分的，奇数时我们需要求解第 k=(m+n)/2 + 1 小数据 ，偶数时我们需要求解 第 k1 = (m+n) / 2 和第 k2=(m+n)/2+1
小，然后 k = (k1+k2)/2
第二是这两个数组并没有合并，我们需要两个没有完全排好序的数组的第k小数，可以分别在两个数组中求第 k/2 小的数进行比较，这就和上面粘贴的分析相结合了。
第三是有可能其中一个数组长度较小，小于 k/2,这是我们就需要在程序中进行判断了，每次都将长度较小的数组置于，传递参数的第一个位置，然后江数组长度与 k/2 比较，如果m>k/2，就直接选取第 pa = k/2小数据，不然就取第一个数组的长度 pa = m，pb = k-pa，然后将A[pa-1]于B[pb-1]（第pb小对应数组的位置应该为pb-1）进行比较,这里痛上面的分析过程
代码：
1 class Solution { 2 public: 3 double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) { 4 int total = nums1.size()+nums2.size(); 5 if(total%2 == 0){ //判断奇偶 6 return (finKth(nums1,nums2,total/2)+finKth(nums1,nums2,total/2+1))/2; 7 } 8 else{ 9 return finKth(nums1,nums2,total/2+1); 10 } 11 } 12 public: 13 double finKth(vector<int> nums1,vector<int> nums2,int k){ // 寻找第k小 14 if( nums1.size() > nums2.size()){ // 将nums1永远作为长度较小的数组 15 return finKth(nums2,nums1,k); 16 } 17 if( nums1.size() == 0 ){ //如果其中一个数组长度为0则第k小就是nums2的第k小 18 return nums2[k-1]; 19 } 20 if(k == 1){ //k=1 说明 一种情况是 两个数组长度都为 1 这是 需要求 （1+1）/2 直接返回两个数组中较小的一个 21 return nums1[0]<nums2[0]?nums1[0]:nums2[0]; // 另一种情况是 每次递归都会去除一部分元素，使得第k小变成第k-p小 当k-p为一时，就可以返回，两个数组nums1[0],nums2[0]中较小的一个了 22 } 23 int findKsa = nums1.size() <k/2 ? nums1.size() : k/2; 24 int findKsb = k-findKsa; 25 if(nums1[findKsa-1]<nums2[findKsb-1]){ 26 return finKth(vector<int>(nums1.begin()+findKsa,nums1.end()),nums2,k-findKsa); 27 } //对这里的vector向量的传递做个说明：因为每次都需要去除一部分数据 ，所以使用 vector 的 begin 和 end 方法截取中间的一部分元素 28 else if(nums1[findKsa-1]>nums2[findKsb-1]){ 29 return finKth(nums1,vector<int>(nums2.begin()+findKsb,nums2.end()),k-findKsb); 30 } 31 else{ 32 return nums1[findKsa-1]; 33 } 34 } 35 };
在这里说说自己做题的感觉，每次看到题都没有思路，做题只是能看懂别人的思路和代码········希望自己逐渐进步，直到可以独立作出大部分的题目（可以自己独立写出自己的的思路）