LeetCode-4.Median of Two Sorted Arrays（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)).

You may assume nums1 and nums2 cannot be both empty.

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

我的解法：

       题目对时间复杂度有要求，我想我自己写的排序算法肯定不如python的sort()函数快，所以直接sort，查了一下现在大多数语言中集成的排序函数都是使用Timsort算法（一种结合了合并排序和插入排序的算法），最坏情况下时间复杂度为O（nlogn），所以符合题意。

class Solution: def findMedianSortedArrays(self, nums1, nums2): """ :type nums1: List[int] :type nums2: List[int] :rtype: float """ l=sorted(nums1+nums2) a=len(l) if a%2==0: return (l[int(a/2-1)]+l[int(a/2)])/2.0 else: return l[a//2]

当然这种方法也学不到什么东西，于是又写了一个java版的，速度出奇的好。由于两个数组都是排好序的，于是可以一边排序一边看是否到达中间位置，边排边记录，这样不用全部遍历就可以找到中位数了。

class Solution { public double findMedianSortedArrays(int[] nums1, int[] nums2) { int len = (nums1.length + nums2.length) / 2 + 1; int i=0; int j=0; int count = 0; int left = 0; int right = 0; while(i < nums1.length && j < nums2.length){ if(nums1[i] >= nums2[j]){ left = right; right = nums2[j]; j++; count++; } else{ left = right; right = nums1[i]; i++; count++; } if(count==len){ if((nums1.length + nums2.length) % 2 != 0){ return right; } else{ return (double)(left + right)/2; } } } while(count<len){ if(i < nums1.length){ left = right; right = nums1[i]; i++; count++; } else if(j < nums2.length){ left = right; right = nums2[j]; j++; count++; } } if((nums1.length + nums2.length) % 2 != 0){ return right; } else{ return (double)(left + right)/2; } } }